数据结构树之二分查找树

二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树。
没有键值相等的节点（no duplicate nodes）。

二叉查找树的性质：

　　二叉查找树本质上是一种二叉树，所以上章讲的二叉树的性质他都有。

二叉查找树的思想：

　　二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，O(log(n)).

二叉查找树的操作：

　　/*二叉树的链式定义*/

1 #define DataType int
2 //二叉树的前序遍历
3 typedef struct BiTNode    //二元查找树的节点
4 {
5     DataType m_Value;
6     BiTNode *m_pLeft;
7     BiTNode *m_pRight;
8 }BiTNode;

　　//创建二元查找树，相当于一个个的插入

 1 void addBSTreeNode(BiTNode *&pCurrent,DataType value)
 2 {
 3     if(NULL == pCurrent)    //如果是空的话就创建节点
 4     {
 5         BiTNode *pBSTree = new BiTNode();
 6         pBSTree->m_pLeft  = NULL;
 7         pBSTree->m_pRight = NULL;
 8         pBSTree->m_Value = value;
 9         pCurrent = pBSTree;
10     }
11     else
12     {
13         if(pCurrent->m_Value > value)
14         {
15             addBSTreeNode(pCurrent->m_pLeft,value);
16         }
17         else if(pCurrent->m_Value < value)
18         {
19             addBSTreeNode(pCurrent->m_pRight,value);
20         }
21         else
22         {
23             cout << "重复插入";
24         }
25     }
26 }

　　//二分查找树的搜索，时间复杂度O(logn)

 1 BiTNode * searchBSTreeNode(BiTNode *pCurrent,DataType value)
 2 {
 3     if(pCurrent == NULL || pCurrent->m_Value == value)
 4     {
 5         return pCurrent;
 6     }
 7     if(pCurrent->m_Value > value)
 8     {
 9         return searchBSTreeNode(pCurrent->m_pLeft,value);
10     }
11     else
12     {
13         return searchBSTreeNode(pCurrent->m_pRight,value);
14     }
15 }

　　//返回二叉查找树中的最小值

1 BiTNode * getMinValueFromBSTree(BiTNode *pCurrent)
2 {
3     while(pCurrent->m_pLeft)
4         pCurrent = pCurrent->m_pLeft;
5     return pCurrent;
6 }

　　//返回二叉查找树中的最大值

1 BiTNode * getMaxValueFromBSTree(BiTNode *pCurrent)
2 {
3     while(pCurrent->m_pRight)
4         pCurrent = pCurrent->m_pRight;
5     return pCurrent;
6 }

　　//返回二叉查找树中的一个节点的后继结点

 1 BiTNode * getSuccessorNode(BiTNode *pCurrent,BiTNode *x)
 2 {
 3     if(!x||!pCurrent)
 4         return NULL;
 5     //如果x节点的右子树不为空，那么后继结点一定是右子树的最左结点
 6     if(x->m_pRight)
 7         return getMinValueFromBSTree(x->m_pRight);
 8     //如果是空节点
 9     while(pCurrent)
10     {
11         if(x->m_Value < pCurrent->m_Value)                //如果比正在检查的节点小，
12             if(getMaxValueFromBSTree(pCurrent->m_pLeft)->m_Value == x->m_Value)    //根节点只有可能是他左子树的最大节点的后继结点
13                 return pCurrent;
14             else
15                 pCurrent = pCurrent->m_pLeft;
16         else
17                 pCurrent = pCurrent->m_pRight;
18     }
19     return pCurrent;
20 }

//返回二叉查找树中的一个节点的前驱结点

 1 BiTNode * getPredecessorNode(BiTNode *pCurrent,BiTNode *x)
 2 {
 3     if(!x||!pCurrent)
 4         return NULL;
 5     //如果x节点的左子树不为空，那么后继结点一定是左子树的最右结点
 6     if(x->m_pLeft)
 7         return getMaxValueFromBSTree(x->m_pLeft);
 8     //如果是空节点
 9     while(pCurrent)
10     {
11         if(x->m_Value > pCurrent->m_Value)                                            //如果比正在检查的节点小，
12             if(getMinValueFromBSTree(pCurrent->m_pRight)->m_Value == x->m_Value)    //根节点只有可能是他右子树的最小结点的前驱结点
13                 return pCurrent;
14             else
15                 pCurrent = pCurrent->m_pRight;
16         else
17                 pCurrent = pCurrent->m_pLeft;
18     }
19     return pCurrent;
20 }

　　//返回一个结点的双亲结点

 1 BiTNode * getParentsNode(BiTNode *pCurrent,BiTNode * x)
 2 {
 3     if(!pCurrent || pCurrent == x ||!x)    //根为空或者就是根节点，则无父节点
 4         return NULL;
 5     while(pCurrent)
 6     {
 7         if(pCurrent->m_pLeft == x || pCurrent->m_pRight == x)
 8             return pCurrent;
 9         if(x->m_Value < pCurrent->m_Value)
10             pCurrent = pCurrent->m_pLeft;
11         else
12             pCurrent = pCurrent->m_pRight;
13     }
14     return NULL;
15 }

　　//删除二叉查找树中一个值为指定值的结点---这个有点长，主要是有些重复的操作可以封装到函数中去，我没有！

  1 void deleteNodeFromBSTreeNode(BiTNode *&pCurrent,DataType value)
  2 {
  3     if(!pCurrent)
  4         return;
  5     BiTNode *fitNode = searchBSTreeNode(pCurrent,value);    //找到要删除的结点
  6     if(!fitNode)                                            //是NULL，直接返回。没找到要删除的结点
  7         return ;
  8     BiTNode *parents = getParentsNode(pCurrent,fitNode),*temp = NULL;    //得到要删除结点的父亲结点
  9     if(!fitNode->m_pLeft)    //如果左结点为空
 10     {
 11         if(parents)
 12         {
 13             if(fitNode == parents->m_pLeft)    //如果是父结点的左结点
 14             {
 15                 parents->m_pLeft = fitNode->m_pRight;
 16             }
 17             else
 18             {
 19                 parents->m_pRight = fitNode->m_pRight;
 20             }
 21         }
 22         else    //没有父结点，那要删除的就是根节点
 23         {
 24             pCurrent = fitNode->m_pRight;
 25         }
 26     }
 27     else if(!fitNode->m_pRight)        //如果右结点为空
 28     {
 29         if(parents)
 30         {
 31             if(fitNode == parents->m_pLeft)    //如果是父结点的左结点
 32             {
 33                 parents->m_pLeft = fitNode->m_pLeft;
 34             }
 35             else
 36             {
 37                 parents->m_pRight = fitNode->m_pLeft;
 38             }
 39         }
 40         else    //没有父结点，那要删除的就是根节点
 41         {
 42             pCurrent = fitNode->m_pLeft;
 43         }
 44     }
 45     else //左右孩子都不为空
 46     {
 47         //找到右子树中左边的的结点---即右子树最小值结点
 48         temp =  getMinValueFromBSTree(fitNode->m_pRight);
 49         if(fitNode->m_pRight != temp)    
 50         {
 51             BiTNode *parents1 = getParentsNode(pCurrent,temp);
 52             if(parents1)
 53             {
 54                 //肯定是在父结点的左结点上
 55                 parents1->m_pLeft = temp->m_pRight;
 56             }
 57             else
 58             {
 59                 //不可能没有父结点了
 60             }
 61             temp->m_pRight = fitNode->m_pRight;
 62             temp->m_pLeft  = fitNode->m_pLeft;
 63             if(parents)
 64             {
 65                 if(parents->m_pLeft == fitNode)
 66                 {
 67                     parents->m_pLeft =  temp;
 68                 }
 69                 else
 70                 {
 71                     parents->m_pRight = temp;
 72                 }
 73             }
 74             else
 75             {
 76                 pCurrent = temp;
 77             }
 78         }
 79         else
 80         {
 81             if(parents)
 82             {
 83                 if(parents->m_pLeft == fitNode)
 84                 {
 85                     parents->m_pLeft =  temp;
 86                     temp ->m_pLeft = fitNode->m_pLeft;
 87                 }
 88                 else
 89                 {
 90                     parents->m_pRight = temp;
 91                     temp ->m_pLeft = fitNode->m_pLeft;
 92                 }
 93             }
 94             else
 95             {
 96                 pCurrent = temp;
 97             }
 98         }
 99     }
100 }

　　//以下是对二叉查找树的操作实例

 1 int main()
 2 {
 3     BiTNode * root = NULL,*p;
 4     addBSTreeNode(root,15);
 5     addBSTreeNode(root,6);
 6     addBSTreeNode(root,18);
 7     addBSTreeNode(root,3);
 8     addBSTreeNode(root,7);
 9     addBSTreeNode(root,17);
10     addBSTreeNode(root,20);
11     addBSTreeNode(root,2);
12     addBSTreeNode(root,4);
13     addBSTreeNode(root,13);
14     addBSTreeNode(root,9);
15     p = searchBSTreeNode(root,18);
16     if(p)    cout << &p << ":" << p->m_Value << endl;
17     else    cout << "不存在！" << endl;
18     cout << "最大值:" <<getMaxValueFromBSTree(root)->m_Value << endl;
19     cout << "最小值:" <<getMinValueFromBSTree(root)->m_Value << endl;
20     cout << "2后继结点值为：" << getSuccessorNode(root,searchBSTreeNode(root,2))->m_Value << endl;
21     cout << "3后继结点值为：" << getSuccessorNode(root,searchBSTreeNode(root,3))->m_Value << endl;
22     cout << "4后继结点值为：" << getSuccessorNode(root,searchBSTreeNode(root,4))->m_Value << endl;
23     cout << "6后继结点值为：" << getSuccessorNode(root,searchBSTreeNode(root,6))->m_Value << endl;
24     cout << "7后继结点值为：" << getSuccessorNode(root,searchBSTreeNode(root,7))->m_Value << endl;
25     cout << "9后继结点值为：" << getSuccessorNode(root,searchBSTreeNode(root,9))->m_Value << endl;
26     cout << "13后继结点值为：" << getSuccessorNode(root,searchBSTreeNode(root,13))->m_Value << endl;
27     cout << "15后继结点值为：" << getSuccessorNode(root,searchBSTreeNode(root,15))->m_Value << endl;
28     cout << "17后继结点值为：" << getSuccessorNode(root,searchBSTreeNode(root,17))->m_Value << endl;
29     cout << "18后继结点值为：" << getSuccessorNode(root,searchBSTreeNode(root,18))->m_Value << endl;
30 
31 
32     cout << "3前驱结点值为：" << getPredecessorNode(root,searchBSTreeNode(root,3))->m_Value << endl;
33     cout << "4前驱结点值为：" << getPredecessorNode(root,searchBSTreeNode(root,4))->m_Value << endl;
34     cout << "6前驱结点值为：" << getPredecessorNode(root,searchBSTreeNode(root,6))->m_Value << endl;
35     cout << "7前驱结点值为：" << getPredecessorNode(root,searchBSTreeNode(root,7))->m_Value << endl;
36     cout << "9前驱结点值为：" << getPredecessorNode(root,searchBSTreeNode(root,9))->m_Value << endl;
37     cout << "13前驱结点值为：" << getPredecessorNode(root,searchBSTreeNode(root,13))->m_Value << endl;
38     cout << "15前驱结点值为：" << getPredecessorNode(root,searchBSTreeNode(root,15))->m_Value << endl;
39     cout << "17前驱结点值为：" << getPredecessorNode(root,searchBSTreeNode(root,17))->m_Value << endl;
40     cout << "18前驱结点值为：" << getPredecessorNode(root,searchBSTreeNode(root,18))->m_Value << endl;
41     cout << "20前驱结点值为：" << getPredecessorNode(root,searchBSTreeNode(root,20))->m_Value << endl;
42 
43     deleteNodeFromBSTreeNode(root,15);
44     inOrderVisitUseRecur(root);
45     cout << endl;
46     return 0;
47 }

　　//以上代码全部本人手工敲上去的，如有错误请留言。如若转载，请注明出处！