Chinaunix首页 | 论坛 | 博客
  • 博客访问: 31571
  • 博文数量: 26
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 300
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
  • 认证徽章:
文章分类

全部博文(26)

文章存档

2018年(24)

2017年(1)

我的朋友

分类: C/C++

2018-06-08 23:45:30

不多说了,又是忘掉了这个东西,手动扣点代码,找找感觉
二叉查找树,首先,它得是棵树,对吧,而且还是个二叉树对吧,大体长这个样子

呃呃,为了后面省事,这张直接给出了平衡二叉树,那个是一种特殊的二叉查找树,后续会撸源码,这次只说二叉查找树。好的,回到上面的树,首先这棵树是由各个节点组成的(这不废话),然后每个节点只有两个出度,分别为左孩子以及右孩子(两个指针,指向相同的节点),还有一个重要的性质是,对于某一节点其左子树上的所有节点全部小于它的值,其右子树上的所有节点值全部都大于其值,其定义如下:

点击(此处)折叠或打开

  1. struct Node{
  2.     struct Node *left;
  3.     struct Node *right;
  4.     int val;
  5.     Node(int x):val(x), left(NULL), right(NULL){}
  6. };
只有这一个结构只能保证有左右两个孩子,不能保证数值大小的性质,这就要在我们插入的时候费点心思了,代码如下(注:我是把该树建了一个类,第一段代码时.h文件,所有操作在里面完成,后面不再赘述):

点击(此处)折叠或打开

  1. #ifndef BSTTREE_H
  2. #define BSTTREE_H
  3. #include <iostream>
  4. #include <stack>
  5. struct Node{
  6.     struct Node *left;
  7.     struct Node *right;
  8.     int val;
  9.     Node(int x):val(x), left(NULL), right(NULL){}
  10. };

  11. class BSTTree
  12. {
  13. public:
  14.     BSTTree();
  15.     ~BSTTree();
  16.     void preOrderWithRecur(struct Node *node);
  17.     void preOrderNon_Recur(struct Node *node);
  18.     void inOrderWithRecur(struct Node *node);
  19.     void inOrderNon_Recur(struct Node *node);
  20.     void postOrderWithRecur(struct Node *node);
  21.     void postOrderNon_Recur(struct Node *node);
  22.     bool isExist(struct Node *node, int k);
  23.     bool insert(struct Node *node, int k);
  24.     int getHeight(struct Node *node);
  25.     bool delNode(struct Node *node, int k);
  26.     struct Node *root;
  27. private:
  28.     bool delRoot();
  29.     bool delNodeLeftNULL(struct Node *parent, struct Node *node);
  30.     bool delNodeRightNULL(struct Node *parent, struct Node *node);
  31.     bool delRootLeftNULL();
  32.     bool delRootRightNULL();

  33. };

  34. #endif // BSTTREE_H
插入代码如下,过程就是从根找起,直到找到自己的位置~~~

点击(此处)折叠或打开

  1. bool BSTTree::isExist(Node *node, int k){
  2.     struct Node *p = node;
  3.     while(p){
  4.         if(p->val == k) return true;
  5.         else if(p->val > k) p = p->left;
  6.         else p = p->right;
  7.     }
  8.     return false;
  9. }
  10. bool BSTTree::insert(struct Node *node, int k){
  11.     if(isExist(node, k))
  12.         return false;
  13.     struct Node *p = node, *parent = NULL;
  14.     while(p){
  15.         parent = p;
  16.         if(p->val > k) p = p->left;
  17.         else p = p->right;
  18.     }
  19.     p = new struct Node(k);
  20.     if(root == NULL){ root = p; return true;}
  21.     else if(parent->val > p->val) parent->left = p;
  22.     else parent->right = p;
  23.     return true;
  24. }
这里特殊情况就是在树为空的时候,要判断一下(因为那时候祖宗还没出现。。。)
接下来讲一下删除,相信大家通过.h文件已经了解到,我是分了好多情况进行讨论来实现的,(因为自己实力有限,看着各种嵌套有点乱)总体来讲,分成两个部分,一个是删除根节点,一个是删除非根节点,因为如果删除非根节点的话,就需要知道其父节点信息,所以分了一下,再有就是在这两大类下面又各自分了两类--->左子树为空,右子树为空,具体代码如下:

点击(此处)折叠或打开

  1. bool BSTTree::delNode(struct Node *node, int k){
  2.     struct Node *parent, *child;
  3.     if(root == NULL) return false;
  4.     if(root->val == k) return delRoot();
  5.     node = root;
  6.     while(node){
  7.         if(node->val == k) break;
  8.         parent = node;
  9.         if(node->val > k) node = node->left;
  10.         else node = node->right;
  11.     }
  12.     if(node == NULL) return false;
  13.     if(node->left== NULL && node->right == NULL){
  14.         if(node == parent->left) parent->left = NULL;
  15.         else parent->right = NULL;
  16.         delete node;
  17.         node = NULL;
  18.         return true;
  19.     }else if(node->left==NULL)
  20.         return delNodeLeftNULL(parent, node);
  21.     else if(node->right== NULL)
  22.         return delNodeRightNULL(parent, node);
  23.     else{
  24.         parent = node, child = node->right;
  25.         int temp;
  26.         while(child->left){ parent = child; child = child->left;}
  27.         temp=node->val; node->val = child->val; child->val = temp;
  28.         if(child == parent->left) parent->left = child->right;
  29.         else parent->right = child->right;
  30.         delete child, child = NULL;
  31.         return true;
  32.     }
  33. }
  34. bool BSTTree::delNodeLeftNULL(struct Node *parent, struct Node *node){
  35.     if(parent->left == node) parent->left = node->right;
  36.     else parent->right = node->right;
  37.     delete node;
  38.     node = NULL;
  39.     return true;
  40. }
  41. bool BSTTree::delNodeRightNULL(struct Node *parent, struct Node *node){
  42.     if(parent->left == node) parent->left = node->left;
  43.     else parent->right = node->left;
  44.     delete node;
  45.     node = NULL;
  46.     return true;
  47. }
  48. bool BSTTree::delRoot(){
  49.     if(root->left == NULL && root->right == NULL){
  50.         delete root;
  51.         root = NULL;
  52.         return true;
  53.     }else if(root->left == NULL){
  54.         return delRootLeftNULL();
  55.     }else if(root->right == NULL){
  56.         return delRootRightNULL();
  57.     }else{
  58.         struct Node *parent = root, *child = root->right;
  59.         int temp;
  60.         while(child->left){ parent = child; child = child->left;}
  61.         temp = root->val; root->val = child->val; child->val = temp;
  62.         if(child == parent->left) parent->left = child->right;
  63.         else parent->right = child->right;
  64.         delete child;
  65.         child = NULL;
  66.         return true;
  67.     }
  68. }
  69. bool BSTTree::delRootLeftNULL(){
  70.     struct Node *p = root;
  71.     root = root->right;
  72.     delete p;
  73.     return true;
  74. }
  75. bool BSTTree::delRootRightNULL(){
  76.     struct Node *p = root;
  77.     root = root->left;
  78.     delete p;
  79.     return true;
  80. }

当左右子树都为空的时候,直接删除就行,但是要注意父节点的指针置为NULL,要不然就是野指针了,知道什么奇奇怪怪的东西就不太好了~~~左(右)子树为空时直接将父节点指针指向对应右(左)子树即可,然后删除节点,至于左右子树都为非空,则需要找到右子树的后继,然后调换数值,后续就按照删除一个左子树为空的节点即可,几种情况分别如下图所示,只列举了右子树为空的情况,其中parent表示被删除节点的父节点指针,child表示要删除节点指针:
左右都为空:

右为空:

左右均非空:


接下直接上遍历代码了,包括递归和非递归的,非递归要借助栈来实现,剩下的感觉只要理解中序遍历就行了,剩下两个都是在它的基础上改了一点:

点击(此处)折叠或打开

  1. void BSTTree::preOrderWithRecur(struct Node *node){
  2.     if(node){
  3.         std::cout<< node->val<<" ";
  4.         preOrderWithRecur(node->left);
  5.         preOrderWithRecur(node->right);
  6.     }
  7. }
  8. void BSTTree::inOrderWithRecur(struct Node *node){
  9.     if(node){
  10.         inOrderWithRecur(node->left);
  11.         std::cout<<node->val<<" ";
  12.         inOrderWithRecur(node->right);
  13.     }
  14. }
  15. void BSTTree::postOrderWithRecur(struct Node *node){
  16.     if(node){
  17.         postOrderWithRecur(node->left);
  18.         postOrderWithRecur(node->right);
  19.         std::cout<<node->val<<" ";
  20.     }
  21. }
  22. void BSTTree::preOrderNon_Recur(struct Node *node){
  23.     std::stack<struct Node*> s;
  24.     struct Node *p = node;
  25.     while(p || !s.empty()){
  26.         while(p){
  27.             std::cout<<p->val<<" ";
  28.             s.push(p);
  29.             p=p->left;
  30.         }
  31.         p = s.top(), s.pop();
  32.         if(p->right) p = p->right;
  33.         else p = NULL;
  34.     }
  35. }
  36. void BSTTree::inOrderNon_Recur(struct Node *node){
  37.     std::stack<struct Node*> s;
  38.     struct Node *p = node;
  39.     while(p || !s.empty()){
  40.         while(p){
  41.             s.push(p);
  42.             p=p->left;
  43.         }
  44.         p = s.top(), s.pop();
  45.         std::cout<<p->val<<" ";
  46.         if(p->right) p = p->right;
  47.         else p = NULL;
  48.     }
  49. }
  50. void BSTTree::postOrderNon_Recur(struct Node *node){
  51.     std::stack<struct Node*> s;
  52.     struct Node *p = node;
  53.     while(p || !s.empty()){
  54.         while(p){
  55.             s.push(p);
  56.             p=p->left;
  57.         }
  58.         p = s.top(), s.pop();
  59.         std::cout<<p->val<<" ";
  60.         if(!s.empty() && p == s.top()->left) p = s.top()->right;
  61.         else p = NULL;
  62.     }
  63. }

还请各位看官老爷多提宝贵意见~~~
阅读(22) | 评论(0) | 转发(0) |
0

上一篇:TCP带外数据

下一篇:平衡二叉搜索树简介

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册