二叉查找树的C++实现

原创作品，转载请注明出处:点我

二叉查找树（Binary Search Tree，BST），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程(其实构建BST的过程就是对数据进行快速排序的过程,也就是快排算法)。所以通常可以通过构建一棵二叉查找树来对数据进行排序，其时间复杂度为O(nlogn),对BST进行搜索，插入和删除的时间复杂度即为树的高度,O(logn).

先来看下本文实现的对BST进行的操作。

void create_tree(node **tree,int data);//生成二叉查找树 void mid_travel(node *tree);//中序遍历树 node* find_node(node *tree,int data);//查找 node* find_parent_node(node *tree,int data);//查找data节点的父节点 node* insert_node(node **tree,int data);//插入数据 node* get_min_parent_ptr(node *tree);//获得tree的最小值的父亲指针 node* get_max_patent_ptr(node *tree);//获取tree的最大值的父亲指针 bool delete_node(node **tree,int data);//删除指定的节点

其中，node的定义为：

typedef struct tree_node {     int data;//数据域     struct tree_node *r_child;//左孩子节点     struct tree_node *l_child;//右孩子节点 }node ;

接着来看下BST的生成create_tree(),其中第一个参数是一个二级指针，指向BST的根节点，注意，这里一定要以二级指针的形式传入，不然后构造失败的，第二个参数是用来生成BST的数据。

 1 /*  2  * 生成二叉树  3  * tree:二级指针，指向生成树  4  * data:生成树的数据  5  * 注意：这里只能传入二级指针  6  * author:rio_2607  7  */  8 void create_tree(node **tree,int data)  9 { 10     if(NULL == *tree) 11     { 12         *tree = (node *)malloc(sizeof(node)); 13         (*tree)->data = data; 14         (*tree)->l_child = NULL; 15         (*tree)->r_child = NULL; 16         return; 17     } 18     else if(data < (*tree)->data)//如果小于根节点的数据，则插入到根节点的左子树 19         create_tree(&((*tree)->l_child),data); 20     else if(data > (*tree)->data)//如果大于根节点的数据，则插入到根节点的右子树 21         create_tree(&((*tree)->r_child),data); 22     else 23     { 24         cout << "有重复数据" << endl; 25         return; 26     } 27 }

再来看下对BST进行查找，这很简单，首先拿待查找的数据跟根节点数据进行比较，如果小于根节点数据，则递归的对根节点的左子树进行查找，如果大于根节点的数据，则对右子树递归的进行查找，如果查找大叶子节点还没有查找到，则要查找的数据不存在，代码如下：

 1 /*  2  * 查找data是否存在  3  * 如果存在，返回对应的节点的指针否则返回NULL  4  * author:rio_2607  5  */  6 node* find_node(node *tree, int data)  8 {  9     if(data == tree->data) 10         return tree; 11     else if(data < tree->data && tree->l_child != NULL) 12         //如果data小于根节点的数据，则对左子树进行查找 13         return find_node(tree->l_child,data); 14     else if(data > tree->data && tree->r_child != NULL) 15         //如果data大于根节点的数据，则对右子树进行查找 16         return find_node(tree->r_child,data); 17     return NULL; 18 }

再来看看插入节点：

 1 /*  2  * 在合适的位置插入数据  3  * tree:二级指针，指向二叉搜索树  4  * data:要插入的数据  5  * 返回被插入节点的指针  6  * author:rio_2607  7  */  8 node* insert_node(node **tree,int data)  9 { 10     node *temp = (node *)malloc(sizeof(node)); 11     temp->data = data; 12     temp->l_child = NULL; 13     temp->r_child = NULL; 14  15     if(NULL == *tree)//如果*tree为空，说明tree还没有数据，则直接插入 16     { 17         *tree = temp; 18         return *tree; 19     } 20     else if(data < (*tree)->data)//如果小于根节点的数据，则插入到他的左子树中 21          return insert_node(&((*tree)->l_child),data); 22     else if(data > (*tree)->data)//如果data大于根节点的数据，则插入到右子树中去 23          return insert_node(&((*tree)->r_child),data); 24     else 25     { 26         cout << "不能添加重复数据" << endl; 27         return NULL; 28     } 29 }

其实对于BST，生成，查找，插入都是很简单的递归操作，麻烦的是删除节点。那么应该怎么删除BST的节点呢？

由于BST的特殊性，BST有以下四个很明显的性质：

1、BST的右子树的最小值，没有左子树(如果有的话，就不会是最小值，因为它的所有的左子树上的值都小于根节点的值)

2、BST的左子树的最大值，没有右子树(如果有的话，就不会是最大值，因为它的所有的右子树上的值都大于根节点的值)

3、BST的左子树中的最大值一定位于该左子树中的最右边的节点上

4、BST中的右子树的最小值一定位于该右子树中的最左边的节点上

这四句话怎么理解呢？如下图所示：

以跟节点为例，根节点的右子树的最小值为15，15这个节点位于右子树的最左端，没有左子树，左子树的最大值为12，位于左子树的最右边，没有右子树。

好了，明白了上面的几点的话就可以进行删除节点的操作了。删除节点的操作为：

1、找到要删除的节点p

2、先看下以节点P否存在右子树，如果存在右子树，就找到右子树中的最小值，把这个最小值赋值给要删除的节点，然后把这个找到的最小值节点删除，删除时有些收尾工作

3、如果以节点P没有右子树，那么就找到节点P的左子树的最大值，把这个最大值赋值给要删除的节点，然后把这个最大值节点给删除，删除时有些收尾工作

4、如果以节点P既没有左子树也没有右子树，说明节点P是一个叶子节点，直接删除即可，删除时有些收尾工作

以上图为例，假如要删除节点13，那么先找到节点13的右子树的最小值，这里是节点15，找到节点15之后，把这个节点的数据，也就是15赋值给要删除的节点13，然后把节点15的父节点，这里是19，的左孩子指针指向节点15的右孩子节点，这里是节点17，然后删除节点15，即可。如下图所示：

因为这里既要用到右子树的最小值节点，记为m，也要用到最小值节点的父节点，记为p，所以我们直接找到最小值节点的父节点，这里是节点19,使用以下代码进行操作：

1 //假设要删除的节点为d 2 //最小值节点的父节点为p,最小值节点为m 3 //其中m = p->l_child 4 d->data = m->data 5 p->l_child = m->r_child 6 free(m)

在查找右子树的最小值的父节点的时候，会碰到一种特殊的情况,如下图:

要删除的节点1，先要找到节点1的右子树的最小值节点，就是节点2，但是在这颗右子树中，节点2没有父节点(因为这是节点1的右子树，节点1不包含在这颗右子树当中),此时，最小值节点的父节点就是最小值节点本身，这种情况下，父节点p的l_child节点为空。所以在代码中，要对这种情况进行特殊处理：直接把父节点p的data域赋值给要删除的节点，然后把要删除的节点(这里是节点1)的右孩子指针指向父节点(这里是节点2)的右孩子节点(这里是节点5),然后删除节点2。

以上图为例，假设我们要删除节点13，由于节点13没有右子树，所以我们要找到节点13的左子树(这里由节点10，节点12和节点11组成)的最大值，这里是节点12，找到之后，把最大值节点(节点12)的数据赋值给要删除的节点，这里是节点13，然后把最大直接点的父节点(这里是节点10)的右孩子指针指向最大值节点的左孩子节点(这里是节点11),然后删除最大直接点(节点12).如下图所示：

同样的，在处理这种情况的时候，跟上面一样，也会碰到一种特殊的情况，如下图所示：

要删除节点14，找到他的左子树的最大值，为节点10，但是在这个左子树(不包括节点14)中，节点10没有父节点，或者说节点10的父节点就是他本身，这种情况要单独处理，处理方法跟上面一样。

如果要删除的节点是叶子节点的话，这种情况就很简单了，但是，这一点要注意的是，在把叶子节点删除了之后，要把这个叶子节点的父节点对应的指针域(l_child或者r_child)置为NULL.具体操作看代码。

好了，现在可以上代码了。首先是get_min_parent_ptr()

 1 /*  2  * 返回树中最小值节点的父节点的指针  3  * 最小值一定是位于左子树的叶子节点  4  * author:rio_2607  5  */  6 node* get_min_parent_ptr(node *tree)  7 {  8     if(NULL == tree)  9     { 10         cout << "tree is empty" << endl; 11         return NULL; 12     } 13     //这种情况对应着父节点记为自身的情况 14     if(tree->l_child == NULL) 15         return tree; 16  17     node *tree_temp = tree; 18     node *temp = tree_temp->l_child; 19     while(temp->l_child != NULL) 20     { 21         tree_temp = temp; 22         temp = temp->l_child; 23     } 24  25     return tree_temp; 26  27 }

接下来是get_max_patent_ptr()

 1 /*  2  * 返回树中最大值节点的父节点的指针  3  * 最大值一定是位于右子树的叶子节点  4  * author:rio_2607  5  */  6 node* get_max_patent_ptr(node *tree)  7 {  8     if(NULL == tree)  9     { 10         cout << "tree is empty" << endl; 11         return NULL; 12     } 13     //这种情况对应着父节点记为自身的情况 14     if(tree->r_child == NULL) 15         return tree; 16  17     node *tree_temp = tree; 18     node *temp = tree_temp->r_child; 19     while(temp->r_child != NULL) 20     { 21         tree_temp = temp; 22         temp = temp->r_child; 23     } 24  25     return tree_temp; 26 }

接下来是get_parent_ptr()

 1 /*  2  * 找到指定节点的父节点  3  * 返回父节点的指针,否则返回NULL  4  * 一般只会查找叶子节点的父节点  5  * author:rio_2607  6  */  7 node* find_parent_node(node *tree,int data)  8 {  9     if(data == tree->data) 10         return tree; 11     if(data < tree->data && tree->l_child != NULL) 12     { 13         if(data == tree->l_child->data) 14             return tree; 15         else 16             return find_parent_node(tree->l_child,data); 17     } 18     else if(data > tree->data && tree->r_child != NULL) 19     { 20         if(data == tree->r_child->data) 21             return tree; 22         else 23             return find_parent_node(tree->r_child,data); 24     } 25     return NULL; 26 }

接下来就是具体的删除节点的代码了delete_node():

 1 /*  2  * 删除data节点  3  * author:rio_2607  4  */  5 bool delete_node(node **tree,int value)  6 {  7     node *value_ptr = find_node(*tree,value);  8     if(NULL == value_ptr)  9     { 10         cout << value << " is not in the data" << endl; 11         return false; 12     } 13  14     //如果要删除的数据是叶子节点，先找到这个叶子节点的父节点，把父节点的孩子节点指针清空，再删除叶子节点 15     if(NULL == value_ptr->l_child && NULL == value_ptr->r_child) 16     { 17         //叶子节点一定有父节点,找到父节点 18         node *parent_ptr = find_parent_node(*tree,value); 19         //判断叶子节点是父节点的左节点还有右节点 20         if(parent_ptr->l_child->data == value) 21             parent_ptr->l_child = NULL; 22         else if(parent_ptr->r_child->data == value) 23             parent_ptr->r_child = NULL; 24         free(value_ptr); 25         //注意，这里要把根节点的父节点的对应的指针域清空 26         return true; 27     } 28     //如果value_ptr的右子树存在,则找到右子树的最小值 29     if(value_ptr->r_child != NULL) 30     { 31         node *min_parent_ptr = get_min_parent_ptr(value_ptr->r_child); 32         if(min_parent_ptr != NULL && min_parent_ptr->l_child != NULL) 33         { 34             node *delete_ptr = min_parent_ptr->l_child;//右子树的最小值的节点指针 35             value_ptr->data = delete_ptr->data;//把要删除的节点的数据域的值赋值为右子树的最小值 36             //把最小值的节点的父节点的左子树指向最小值节点的右子树 37             //因为最小值节点没有左子树 38             min_parent_ptr->l_child = delete_ptr->r_child; 39             free(delete_ptr);//删除最小值节点 40             return true; 41         } 42         else if(min_parent_ptr != NULL && NULL == min_parent_ptr->l_child) 43         { 44             //如果min_parent_ptr->l_child为空，说明以value_ptr为根节点的树没有左子树 45             //则value_ptr的右子树的根节点就是最小值 46             value_ptr->data = min_parent_ptr->data; 47             value_ptr->r_child = min_parent_ptr->r_child; 48             free(min_parent_ptr); 49             return true; 50         } 51     } 52     //如果没有右子树有左子树，则找出左子树的最大值 53     else if(NULL == value_ptr->r_child && value_ptr->l_child != NULL) 54     { 55         node *max_parent_ptr = get_max_patent_ptr(value_ptr->l_child); 56         if(max_parent_ptr != NULL && max_parent_ptr->r_child != NULL) 57         { 58             node *delete_ptr = max_parent_ptr->r_child;//左子树的最大值节点指针 59             value_ptr->data = delete_ptr->data;//把要删除节点的数据域赋值为左子树的最大值 60             //把最大值节点的父节点的右子树赋值为最大值节点的左子树 61             //因为最大值节点没有右子树 62             max_parent_ptr->r_child = delete_ptr->l_child; 63             free(delete_ptr); 64             return true; 65         } 66         else if(max_parent_ptr != NULL && NULL == max_parent_ptr->r_child) 67         { 68             //如果max_parent_ptr->r_child为空，说明value_ptr没有右子树 69             //则value_ptr的左子树的根节点就是最大值 70             value_ptr->data = max_parent_ptr->data; 71             value_ptr->l_child = max_parent_ptr->l_child; 72             free(max_parent_ptr); 73             return true; 74         } 75     } 76  77     return false; 78 }