1. 首页
  2. IT资讯

二叉排序树

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree),是指一棵空树或者具有下列性质的二叉树: 

  • 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;  
  • 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 任意节点的左、右子树也分别为二叉查找树;
  • 没有键值相等的节点。

从上述定义可知,二叉排序树是记录之间满足一定次序关系的二叉树。下面介绍如何构建一棵二叉排序树,以及遍历,插入,查找,也会简单的介绍删除结点操作。

构造一棵排序二叉树,则一定要根据其定义来实现。下面给出相关代码:

[cpp]view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1. #include<iostream>  
  2. using namespace std;  
  3. typedef struct bstNote {  
  4.     int data;  
  5.     struct bstNote *lchild, *rchild;  
  6. }*bstTree;  
  7.   
  8. void insertNote(bstTree &bst, int _data) {  
  9.     if (bst == NULL) {  
  10.         bst = new bstNote;  
  11.         bst->data = _data;  
  12.         bst->lchild = bst->rchild = NULL;  
  13.         return;  
  14.     }  
  15.     if (bst->data == _data) {  
  16.         exit(-1);  
  17.     }  
  18.       
  19.     else if(bst->data > _data)   
  20.         insertNote(bst->lchild, _data);  
  21.       
  22.       else  
  23.           insertNote(bst->rchild, _data);  
  24. }  
  25. void createBST(bstTree  &bst,int *arry,int length){  
  26.     bst = NULL;  
  27.   
  28.     for (int i = 0; i < length; i++) {  
  29.         insertNote(bst, arry[i]);  
  30.     }  
  31. }  
  32. void preOrder(bstTree bst) {  
  33. if (bst == NULL) {  
  34.         return;  
  35.     }  
  36.   
  37.         cout << bst->data << ” “;  
  38.         preOrder(bst->lchild);  
  39.         preOrder(bst->rchild);  
  40.       
  41. }  
  42. void inOrder(bstTree bst) {  
  43.     if (bst == NULL) {  
  44.         return;  
  45.     }  
  46.     inOrder(bst->lchild);  
  47.     cout << bst->data << ” “;  
  48.     inOrder(bst->rchild);  
  49. }  
  50. void postOrder(bstTree bst) {  
  51.     if (bst == NULL) {  
  52.         return;  
  53.     }  
  54.     postOrder(bst->lchild);  
  55.     postOrder(bst->rchild);  
  56.     cout << bst->data << ” “;  
  57. }  
  58. bstTree searchBST(bstTree bst, int key) {  
  59.     if (bst == NULL)  
  60.         return false;  
  61.     else if (bst->data == key) {  
  62.         cout << “查找成功:”<<bst->data<< endl;  
  63.         return bst;  
  64.     }  
  65.     else if(bst->data>key)  
  66.         return searchBST(bst->lchild, key);   
  67.     else  
  68.         return searchBST(bst->rchild, key);  
  69. }  
  70. int main(){  
  71.     bstTree bst;  
  72.     int arry[] = {4,5,2,1,3,10,7,8,6,0};  
  73.     int length = sizeof(arry) / sizeof(int);  
  74.     createBST(bst, arry, length);  
  75.     cout << “PreOrder:” << endl;;  
  76.     preOrder(bst);  
  77.     cout << endl;  
  78.     cout << “InOrder:” << endl;  
  79.     inOrder(bst);  
  80.     cout << endl;  
  81.     cout << “PostOrder:” << endl;;  
  82.     postOrder(bst);  
  83.     cout << endl;  
  84.     searchBST(bst,6);   
  85.     insertNote(bst, 9);  
  86.     preOrder(bst);  
  87.     cout << endl;  
  88.     inOrder(bst);  
  89. }  

上面的代码比较简单的实现构造,遍历,查找。
但是在二叉查找树删去一个结点,分三种情况讨论:(如下参考维基百科:点击打开链接)
1.若*p结点为叶子结点,即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则只需修改其双亲结点的指针即可。
2.若*p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点*f的左子树(当*p是左子树)或右子树(当*p是右子树)即可,作此修改也不破坏二叉查找树的特性。

3.若*p结点的左子树和右子树均不空。在删去*p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法:其一是令*p的左子树为*f的左/右(依*p是*f的左子树还是右子树而定)子树,*s为*p左子树的最右下的结点,而*p的右子树为*s的右子树;其二是令*p的直接前驱(in-order predecessor)或直接后继(in-order successor)替代*p,然后再从二叉查找树中删去它的直接前驱(或直接后继),该种情况较为复杂,如下图示。

二叉排序树

算法:

[cpp]view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1. Status DeleteBST(BiTree &T, KeyType key){  
  2.   //若二叉查找树T中存在关键字等于key的数据元素时,则删除该数据元素,并返回  
  3.   //TRUE;否则返回FALSE  
  4.   if(!T)   
  5.     return false;   //不存在关键字等于key的数据元素  
  6.   else{  
  7.     if(key == T->data.key) {     //  找到关键字等于key的数据元素  
  8.       return Delete(T);  
  9.     }  
  10.     else if(key < T->data.key)  
  11.       return DeleteBST(T->lchild, key);  
  12.     else  
  13.       return DeleteBST(T->rchild, key);  
  14.   }  
  15. }  
  16. Status Delete(BiTree &p){  
  17.   //该节点为叶子节点,直接删除  
  18.   BiTree *q, *s;  
  19.   if (!p->rchild && !p->lchild)  
  20.   {  
  21.       delete p;  
  22.       p = NULL;  
  23.   }  
  24.   else if(!p->rchild){   //右子树空则只需重接它的左子树  
  25.     q=p->lchild;  
  26.     p->data = p->lchild->data;  
  27.     p->lchild=p->lchild->lchild;  
  28.     p->rchild=p->lchild->rchild;  
  29.   
  30.     delete q;  
  31.   }  
  32.   else if(!p->lchild){   //左子树空只需重接它的右子树  
  33.     q=p->rchild;  
  34.     p->data = p->rchild->data;  
  35.     p->lchild=p->rchild->lchild;  
  36.     p->rchild=p->rchild->rchild;  
  37.   
  38.     delete q;  }  
  39.   else//左右子树均不空  
  40.     q=p;   
  41.     s=p->lchild;  
  42.     while(s->rchild){   
  43.       q=s;   
  44.       s=s->rchild;  
  45.     }   //转左,然后向右到尽头  
  46.     p->data = s->data;    //s指向被删结点的“前驱”  
  47.     if(q!=p)      
  48.       q->rchild = s->lchild;  //重接*q的右子树  
  49.     else   
  50.       q->lchild = s->lchild;  //重接*q的左子树  
  51.     delete s;  
  52.   }  
  53.   return true;  
  54. }  

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/29876893/viewspace-1988155/,如需转载,请注明出处,否则将追究法律责任。

主题测试文章,只做测试使用。发布者:℅傍ㄖ免沦陷dε鬼,转转请注明出处:http://www.cxybcw.com/192024.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code