浅析二叉树的遍历以及二叉查找树

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

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

点击(此处)折叠或打开

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. 
    
12. class BSTTree
    
13. {
    
14. public:
    
15.     BSTTree();
    
16.     ~BSTTree();
    
17.     void preOrderWithRecur(struct Node *node);
    
18.     void preOrderNon_Recur(struct Node *node);
    
19.     void inOrderWithRecur(struct Node *node);
    
20.     void inOrderNon_Recur(struct Node *node);
    
21.     void postOrderWithRecur(struct Node *node);
    
22.     void postOrderNon_Recur(struct Node *node);
    
23.     bool isExist(struct Node *node, int k);
    
24.     bool insert(struct Node *node, int k);
    
25.     int getHeight(struct Node *node);
    
26.     bool delNode(struct Node *node, int k);
    
27.     struct Node *root;
    
28. private:
    
29.     bool delRoot();
    
30.     bool delNodeLeftNULL(struct Node *parent, struct Node *node);
    
31.     bool delNodeRightNULL(struct Node *parent, struct Node *node);
    
32.     bool delRootLeftNULL();
    
33.     bool delRootRightNULL();
    
34. 
    
35. };
    
36. 
    
37. #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. }

还请各位看官老爷多提宝贵意见~~~