[关闭]
@Lin-- 2020-02-15T10:18:30.000000Z 字数 10813 阅读 355

二叉搜索树

DataStruct

零、定义：

每个节点至多有两个孩子，且左孩子的值小于自己，右孩子的值大于自己。

  1. struct BST{
  2.   int value;
  3.   struct BST * right;
  4.   struct BST * left;
  5. };

一、创建结点

  1. //build a binary tree (root)
  2. struct BST* BuildBSTNode(int v)
  3. {
  4.   struct BST* node=(struct BST *)malloc(sizeof(struct BST));
  5.   node->value=v;
  6.   node->left=NULL;
  7.   node->right=NULL;
  8.   return node;
  9. }

二、在树中插入已有结点

  1. //insert BSTNode
  2. void InsertBSTNode(struct BST * root,struct BST * node)
  3. {
  4.   if(node->value<root->value&&root->left==NULL)
  5.   {root->left=node;}
  7.   if(node->value>root->value&&root->right==NULL)
  8.   {root->right=node;}
  10.   if(node->value<root->value&&root->left!=NULL)
  11.   {InsertBSTNode(root->left,node);}
  13.   if(node->value>root->value&&root->right!=NULL)
  14.   {InsertBSTNode(root->right,node);}
  15. }

三、寻找结点

  1. //Find a Node whether in a tree
  2. bool FindNode(struct BST *root,int v)
  3. {
  4.   if(root==NULL){return false;}
  6.   if(v==root->value)
  7.   {return true;}
  8.   else if(v<root->value)
  9.   {return FindNode(root->left,v);}
  10.   else
  11.   {return FindNode(root->right,v);}
  12. }

四、寻找父节点

  1. //Find a node's parent in a tree
  2. struct BST * FindParent(struct BST * root,int v)
  3. {
  4.   if(root->value==v){return NULL;}
  6.   if(v<root->value)
  7.   {
  8.     if(v==root->left->value){return root;}
  9.     else{return FindParent(root->left,v);}
  10.   }
  11.   else
  12.   {
  13.     if(v==root->right->value){return root;}
  14.     else{return FindParent(root->right,v);}
  15.   }
  16. }

五、删除结点

结点有三种情况：

1.没有孩子

直接删除

  1.       //结点为叶子结点，左右子树为空。直接删除
  2.       if(pre->left==NULL&&pre->right==NULL)
  3.       {
  4.         if(parent->left!=NULL&&parent->left->value==v)
  5.         {
  6.           free(parent->left);parent->left=NULL;
  7.           free(pre);
  8.           pre=NULL;
  9.         }
  10.         else
  11.         {
  12.           free(parent->right);parent->right=NULL;
  13.           free(pre);
  14.           pre=NULL;
  15.         }
  16.       }

2.有单子结点

将其父节点指向待删结点的指针，指向待删结点的单子

  1.       //左子树为空，右子树不空。将该节点的父节点连接其右子树
  2.       else if(pre->left==NULL&&pre->right!=NULL)
  3.       {
  4.         //该节点是父亲节点的左子树
  5.         if(parent->left->value==v)
  6.         {
  7.           parent->left=pre->right;
  8.           free(pre);pre=NULL;
  9.         }
  10.         //该节点是父节点的右子树
  11.         else
  12.         {
  13.           parent->right=pre->right;
  14.           free(pre);pre=NULL;
  15.         }
  16.       }
  17.       //右子树为空，左子树不空。将该节点的父节点连接其左子树
  18.       else if(pre->left!=NULL&&pre->right==NULL)
  19.       {
  20.         //该节点是父亲节点的左子树
  21.         if(parent->left->value==v)
  22.         {
  23.           parent->left=pre->left;
  24.           free(pre);pre=NULL;
  25.         }
  26.         //该节点是父节点的右子树
  27.         else
  28.         {
  29.           parent->right=pre->left;
  30.           free(pre);pre=NULL;
  31.         }
  32.       }

3.有双子结点

自己的值替换成右子树中，最小的值（最左边那个结点），然后将那个被替代的结点删除。

  1.       //左右子树都不空，取右子树中最左的结点代替后删除
  2.       else
  3.       {
  4.         struct BST * temp=&(*pre->right),* tempparent=&(*pre);
  5.         //找到最左的结点
  6.         while(temp->left!=NULL)
  7.         {tempparent=temp;temp=temp->left;}
  8.         //最左结点是叶子结点
  9.         if(temp->right==NULL)
  10.         {
  11.           pre->value=temp->value;//替换到待删结点
  12.           free(pre->right);pre->right=NULL;
  13.           free(temp);temp=NULL;
  14.         }
  15.         //若最左结点还有右子树
  16.         else
  17.         {
  18.           pre->value=temp->value;
  19.           if(tempparent->value==pre->value)
  20.           {pre->right=temp->right;free(temp);temp=NULL;}
  21.           else
  22.           {
  23.             tempparent->left=temp->right;
  24.             free(temp);temp=NULL;
  25.           }
  26.         }
  27.       }

删除操作完整函数

  1. //delete a node in a tree
  2. bool DeleteNode(struct BST *parent,struct BST *pre,int v)
  3. {
  4.   //找不到被删结点
  5.   if(pre==NULL){return false;}
  6.   //找得到或还没找到
  7.   else
  8.   {
  9.     //待删结点小于当前节点，树往左走
  10.     if(v<pre->value)
  11.     {
  12.       return DeleteNode(&(*pre),(&*pre)->left,v);
  13.     }
  14.     //待删结点大于当前节点，树往右走
  15.     else if(v>pre->value)
  16.     {
  17.       return DeleteNode(&(*pre),(&*pre)->right,v);
  18.     }
  19.     //找到待删结点
  20.     else
  21.     {
  22.       //结点为叶子结点，左右子树为空。直接删除
  23.       if(pre->left==NULL&&pre->right==NULL)
  24.       {
  25.         if(parent->left!=NULL&&parent->left->value==v)
  26.         {
  27.           free(parent->left);parent->left=NULL;
  28.           free(pre);
  29.           pre=NULL;
  30.         }
  31.         else
  32.         {
  33.           free(parent->right);parent->right=NULL;
  34.           free(pre);
  35.           pre=NULL;
  36.         }
  37.       }
  38.       //左子树为空，右子树不空。将该节点的父节点连接其右子树
  39.       else if(pre->left==NULL&&pre->right!=NULL)
  40.       {
  41.         //该节点是父亲节点的左子树
  42.         if(parent->left->value==v)
  43.         {
  44.           parent->left=pre->right;
  45.           free(pre);pre=NULL;
  46.         }
  47.         //该节点是父节点的右子树
  48.         else
  49.         {
  50.           parent->right=pre->right;
  51.           free(pre);pre=NULL;
  52.         }
  53.       }
  54.       //右子树为空，左子树不空。将该节点的父节点连接其左子树
  55.       else if(pre->left!=NULL&&pre->right==NULL)
  56.       {
  57.         //该节点是父亲节点的左子树
  58.         if(parent->left->value==v)
  59.         {
  60.           parent->left=pre->left;
  61.           free(pre);pre=NULL;
  62.         }
  63.         //该节点是父节点的右子树
  64.         else
  65.         {
  66.           parent->right=pre->left;
  67.           free(pre);pre=NULL;
  68.         }
  69.       }
  70.       //左右子树都不空，取右子树中最左的结点代替后删除
  71.       else
  72.       {
  73.         struct BST * temp=&(*pre->right),* tempparent=&(*pre);
  74.         //找到最左的结点
  75.         while(temp->left!=NULL)
  76.         {tempparent=temp;temp=temp->left;}
  77.         //最左结点是叶子结点
  78.         if(temp->right==NULL)
  79.         {
  80.           pre->value=temp->value;//替换到待删结点
  81.           free(pre->right);pre->right=NULL;
  82.           free(temp);temp=NULL;
  83.         }
  84.         //若最左结点还有右子树
  85.         else
  86.         {
  87.           pre->value=temp->value;
  88.           if(tempparent->value==pre->value)
  89.           {pre->right=temp->right;free(temp);temp=NULL;}
  90.           else
  91.           {
  92.             tempparent->left=temp->right;
  93.             free(temp);temp=NULL;
  94.           }
  95.         }
  96.       }
  97.       return true;
  98.     }
  99.   }
  100. }

六、层次遍历

  1. 用一个队列，初始化将根节点push进去
  2. 打印队头的结点并pop出
  3. 依次将当前节点的左右结点（顺序不能倒）push进去
  4. 步骤2和3循环直至队列为空
  1. //visit a tree LevelOrder
  2. void LevelOrder(struct BST *root)
  3. {
  4.   queue<struct BST*> Q;
  5.   Q.push(root);
  7.   while(Q.empty()!=true)
  8.   {
  9.     printf("%d ",Q.front()->value);
  10.     if(Q.front()->left!=NULL)
  11.     {
  12.       Q.push(Q.front()->left);
  13.     }
  14.     if(Q.front()->right!=NULL)
  15.     {
  16.       Q.push(Q.front()->right);
  17.     }
  18.     Q.pop();
  19.   }
  20. }

七、先序遍历

先访问（打印），后进入子树

递归版本

  1. //visit a tree PreOrder
  2. void PreOrderBST(struct BST * root)
  3. {
  4.   if(root!=NULL)
  5.   {
  6.     printf("%d ",root->value);
  7.     PreOrderBST(root->left);
  8.     PreOrderBST(root->right);
  9.   }
  10. }

非递归版本

  1. 迭代必须用栈，初始化将根结点push进去
  2. 将结点pop出来并打印
  3. 依次push该节点的右左孩子（栈是先进后出，顺序要相反）
  4. 循环步骤2和3直至栈空
  1. //visit a tree PreOrder without recursion
  2. void PreOrderBSTStack(struct BST * root)
  3. {
  4.   if(root==NULL){return;}
  5.   stack<struct BST*> S;
  6.   S.push(root);
  7.   while(S.empty()!=true)
  8.   {
  9.     struct BST *temp=&(*S.top());
  10.     printf("%d ",temp->value);
  11.     S.pop();
  12.     if(temp->right!=NULL)
  13.     {
  14.       S.push(temp->right);
  15.     }
  16.     if(temp->left!=NULL)
  17.     {
  18.       S.push(temp->left);
  19.     }
  20.     free(temp);
  21.   }
  22. }

八、中序遍历

递归版本

  1. //visit a tree InOrder
  2. void InOrderBST(struct BST * root)
  3. {
  4.   if(root!=NULL)
  5.   {
  6.     InOrderBST(root->left);
  7.     printf("%d ",root->value);
  8.     InOrderBST(root->right);
  9.   }
  10. }

非递归版本

中序遍历的顺序是：左->中/根->右。
具体做法是：用一个栈，将左子树一压到底，直到没有左子树，即遇到最左结点，此时便pop出来同时打印，pop出来时，看看其有没有右子树，有的话再push它的右子树。以此循环，直到栈空。

那么对于栈中的结点有两种情况：一是左子树还没压进来，二是左子树已经pop出去了，而这两种情况栈中都没有左子树，所以需要用字典标记当前节点的左子树是否已经是pop出的。

  1. //visit a tree InOrder without recursion
  2. void InOrderBSTStack(struct BST *root)
  3. {
  4.   stack<struct BST*> S;
  5.   map<struct BST*,bool> dict;
  6.   S.push(root);dict[root]=false;
  7.   while(S.empty()!=true)
  8.   {
  9.     struct BST *temp=&(*S.top());
  10.     if(temp->left!=NULL&&dict[temp]!=true)
  11.     {
  12.       S.push(temp->left);
  13.       dict[temp]=true;
  14.       continue;
  15.     }
  16.     printf("%d ",temp->value);
  17.     S.pop();
  18.     if(temp->right!=NULL)
  19.     {
  20.       S.push(temp->right);
  21.       continue;
  22.     }
  23.     free(temp);
  24.   }
  25. }

九、后续遍历

递归版本

  1. //visit a tree PostOrder
  2. void PostOrderBST(struct BST * root)
  3. {
  4.   if(root!=NULL)
  5.   {
  6.     PostOrderBST(root->left);
  7.     PostOrderBST(root->right);
  8.     printf("%d ",root->value);
  9.   }
  10. }

非递归版本

后续遍历的打印顺序是左->右->根。
而且结点要输出会有两种情况：
一是该节点是一个叶子结点，二是该节点的孩子结点都已经输出了。
也就是说，对于一个有子节点的的结点来说，它的子节点要么还没进栈，要么已经输出，而这两种情况栈中都没有它的子节点的存在，所以需要有一个标记来区分一个结点它的子节点是否已经输出。所以，出了一个栈外，还需要有一个字典来存储结点与输出与否之间的映射关系。

  1. //visit a tree PostOrder without recursion
  2. void PostOrderBSTStack(struct BST * root)
  3. {
  4.   if(root==NULL){return ;}
  6.   map<struct BST *,bool> dict;
  7.   stack<struct BST *> S;
  8.   S.push(root);dict[root]=false;
  9.   while(S.empty()!=true)
  10.   {
  11.     struct BST *temp=&(*S.top());
  12.     if((temp->left==NULL&&temp->right==NULL)||dict[temp]==true)
  13.     {
  14.       printf("%d ",temp->value);
  15.       S.pop();
  16.       free(temp);
  17.       continue;
  18.     }
  19.     if(temp->right!=NULL&&dict[temp]!=true)
  20.     {
  21.       S.push(temp->right);
  22.     }
  23.     if(temp->left!=NULL&&dict[temp]!=true)
  24.     { 
  25.       S.push(temp->left);
  26.     }
  27.     dict[temp]=true;
  28.   }
  29. }

十、完整代码

  1. #include<iostream>
  2. #include<queue>
  3. #include<stack>
  4. #include<map>
  5. using namespace std;
  6. struct BST{
  7.   int value;
  8.   struct BST * right;
  9.   struct BST * left;
  10. };
  12. //build a binary tree (root)
  13. struct BST* BuildBSTNode(int v)
  14. {
  15.   struct BST* node=(struct BST *)malloc(sizeof(struct BST));
  16.   node->value=v;
  17.   node->left=NULL;
  18.   node->right=NULL;
  19.   return node;
  20. }
  21. //visit a tree PreOrder
  22. void PreOrderBST(struct BST * root)
  23. {
  24.   if(root!=NULL)
  25.   {
  26.     printf("%d ",root->value);
  27.     PreOrderBST(root->left);
  28.     PreOrderBST(root->right);
  29.   }
  30. }
  31. //visit a tree PreOrder without recursion
  32. void PreOrderBSTStack(struct BST * root)
  33. {
  34.   if(root==NULL){return;}
  35.   stack<struct BST*> S;
  36.   S.push(root);
  37.   while(S.empty()!=true)
  38.   {
  39.     struct BST *temp=&(*S.top());
  40.     printf("%d ",temp->value);
  41.     S.pop();
  42.     if(temp->right!=NULL)
  43.     {
  44.       S.push(temp->right);
  45.     }
  46.     if(temp->left!=NULL)
  47.     {
  48.       S.push(temp->left);
  49.     }
  50.     free(temp);
  51.   }
  52. }
  53. //visit a tree InOrder
  54. void InOrderBST(struct BST * root)
  55. {
  56.   if(root!=NULL)
  57.   {
  58.     InOrderBST(root->left);
  59.     printf("%d ",root->value);
  60.     InOrderBST(root->right);
  61.   }
  62. }
  63. //visit a tree InOrder without recursion
  64. void InOrderBSTStack(struct BST *root)
  65. {
  66.   stack<struct BST*> S;
  67.   map<struct BST*,bool> dict;
  68.   S.push(root);dict[root]=false;
  69.   while(S.empty()!=true)
  70.   {
  71.     struct BST *temp=&(*S.top());
  72.     if(temp->left!=NULL&&dict[temp]!=true)
  73.     {
  74.       S.push(temp->left);
  75.       dict[temp]=true;
  76.       continue;
  77.     }
  78.     printf("%d ",temp->value);
  79.     S.pop();
  80.     if(temp->right!=NULL)
  81.     {
  82.       S.push(temp->right);
  83.       continue;
  84.     }
  85.     free(temp);
  86.   }
  87. }
  88. //visit a tree PostOrder
  89. void PostOrderBST(struct BST * root)
  90. {
  91.   if(root!=NULL)
  92.   {
  93.     PostOrderBST(root->left);
  94.     PostOrderBST(root->right);
  95.     printf("%d ",root->value);
  96.   }
  97. }
  98. //visit a tree PostOrder without recursion
  99. void PostOrderBSTStack(struct BST * root)
  100. {
  101.   if(root==NULL){return ;}
  103.   map<struct BST *,bool> dict;
  104.   stack<struct BST *> S;
  105.   S.push(root);dict[root]=false;
  106.   while(S.empty()!=true)
  107.   {
  108.     struct BST *temp=&(*S.top());
  109.     if((temp->left==NULL&&temp->right==NULL)||dict[temp]==true)
  110.     {
  111.       printf("%d ",temp->value);
  112.       S.pop();
  113.       free(temp);
  114.       continue;
  115.     }
  116.     if(temp->right!=NULL&&dict[temp]!=true)
  117.     {
  118.       S.push(temp->right);
  119.     }
  120.     if(temp->left!=NULL&&dict[temp]!=true)
  121.     {
  122.       S.push(temp->left);
  123.     }
  124.     dict[temp]=true;
  125.   }
  126. }
  127. //insert BSTNode
  128. void InsertBSTNode(struct BST * root,struct BST * node)
  129. {
  130.   if(node->value<root->value&&root->left==NULL)
  131.   {root->left=node;}
  133.   if(node->value>root->value&&root->right==NULL)
  134.   {root->right=node;}
  136.   if(node->value<root->value&&root->left!=NULL)
  137.   {InsertBSTNode(root->left,node);}
  139.   if(node->value>root->value&&root->right!=NULL)
  140.   {InsertBSTNode(root->right,node);}
  141. }
  142. //Find a Node whether in a tree
  143. bool FindNode(struct BST *root,int v)
  144. {
  145.   if(root==NULL){return false;}
  147.   if(v==root->value)
  148.   {return true;}
  149.   else if(v<root->value)
  150.   {return FindNode(root->left,v);}
  151.   else
  152.   {return FindNode(root->right,v);}
  153. }
  154. //Find a node's parent in a tree
  155. struct BST * FindParent(struct BST * root,int v)
  156. {
  157.   if(root->value==v){return NULL;}
  159.   if(v<root->value)
  160.   {
  161.     if(v==root->left->value){return root;}
  162.     else{return FindParent(root->left,v);}
  163.   }
  164.   else
  165.   {
  166.     if(v==root->right->value){return root;}
  167.     else{return FindParent(root->right,v);}
  168.   }
  169. }
  170. //delete a node in a tree
  171. bool DeleteNode(struct BST *parent,struct BST *pre,int v)
  172. {
  173.   //找不到被删结点
  174.   if(pre==NULL){return false;}
  175.   //找得到或还没找到
  176.   else
  177.   {
  178.     //待删结点小于当前节点，树往左走
  179.     if(v<pre->value)
  180.     {
  181.       return DeleteNode(&(*pre),(&*pre)->left,v);
  182.     }
  183.     //待删结点大于当前节点，树往右走
  184.     else if(v>pre->value)
  185.     {
  186.       return DeleteNode(&(*pre),(&*pre)->right,v);
  187.     }
  188.     //找到待删结点
  189.     else
  190.     {
  191.       //结点为叶子结点，左右子树为空。直接删除
  192.       if(pre->left==NULL&&pre->right==NULL)
  193.       {
  194.         if(parent->left!=NULL&&parent->left->value==v)
  195.         {
  196.           free(parent->left);parent->left=NULL;
  197.           free(pre);
  198.           pre=NULL;
  199.         }
  200.         else
  201.         {
  202.           free(parent->right);parent->right=NULL;
  203.           free(pre);
  204.           pre=NULL;
  205.         }
  206.       }
  207.       //左子树为空，右子树不空。将该节点的父节点连接其右子树
  208.       else if(pre->left==NULL&&pre->right!=NULL)
  209.       {
  210.         //该节点是父亲节点的左子树
  211.         if(parent->left->value==v)
  212.         {
  213.           parent->left=pre->right;
  214.           free(pre);pre=NULL;
  215.         }
  216.         //该节点是父节点的右子树
  217.         else
  218.         {
  219.           parent->right=pre->right;
  220.           free(pre);pre=NULL;
  221.         }
  222.       }
  223.       //右子树为空，左子树不空。将该节点的父节点连接其左子树
  224.       else if(pre->left!=NULL&&pre->right==NULL)
  225.       {
  226.         //该节点是父亲节点的左子树
  227.         if(parent->left->value==v)
  228.         {
  229.           parent->left=pre->left;
  230.           free(pre);pre=NULL;
  231.         }
  232.         //该节点是父节点的右子树
  233.         else
  234.         {
  235.           parent->right=pre->left;
  236.           free(pre);pre=NULL;
  237.         }
  238.       }
  239.       //左右子树都不空，取右子树中最左的结点代替后删除
  240.       else
  241.       {
  242.         struct BST * temp=&(*pre->right),* tempparent=&(*pre);
  243.         //找到最左的结点
  244.         while(temp->left!=NULL)
  245.         {tempparent=temp;temp=temp->left;}
  246.         //最左结点是叶子结点
  247.         if(temp->right==NULL)
  248.         {
  249.           pre->value=temp->value;//替换到待删结点
  250.           free(pre->right);pre->right=NULL;
  251.           free(temp);temp=NULL;
  252.         }
  253.         //若最左结点还有右子树
  254.         else
  255.         {
  256.           pre->value=temp->value;
  257.           if(tempparent->value==pre->value)
  258.           {pre->right=temp->right;free(temp);temp=NULL;}
  259.           else
  260.           {
  261.             tempparent->left=temp->right;
  262.             free(temp);temp=NULL;
  263.           }
  264.         }
  265.       }
  266.       return true;
  267.     }
  268.   }
  269. }
  270. //visit a tree LevelOrder
  271. void LevelOrder(struct BST *root)
  272. {
  273.   queue<struct BST*> Q;
  274.   Q.push(root);
  276.   while(Q.empty()!=true)
  277.   {
  278.     printf("%d ",Q.front()->value);
  279.     if(Q.front()->left!=NULL)
  280.     {
  281.       Q.push(Q.front()->left);
  282.     }
  283.     if(Q.front()->right!=NULL)
  284.     {
  285.       Q.push(Q.front()->right);
  286.     }
  287.     Q.pop();
  288.   }
  289. }
  291. int main ()
  292. {
  293.   int a[16]={15,8,30,6,9,17,40,4,7,16,35,49,33,38,34,39};
  294.   struct BST * root=BuildBSTNode(a[0]);
  295.   for(int i=1;i<16;++i)
  296.   {
  297.     struct BST * node=BuildBSTNode(a[i]);
  298.     InsertBSTNode(root,node);
  299.   }
  300.   PostOrderBST(root);printf("\n");
  301.   PostOrderBSTStack(root);
  302. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注