歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

【算法導論】二叉查找樹的操作C++實現

本代碼為算法導論第12章中,偽代碼的C++實現:

  1. #include <iostream>  
  2. #include <vector>  
  3. using namespace std; 
  4. /*二叉查找樹結構*/ 
  5. typedef struct BSTree 
  6.     int node_value; 
  7.     struct BSTree * left; 
  8.     struct BSTree * right; 
  9.     struct BSTree * parent; 
  10. }Tree; 
  11. Tree * root = NULL; 
  12. /*****構造二叉查找樹**********************************************/ 
  13. void  CreateBSTree(Tree * root,int node_value); 
  14. Tree * CreateBSTree(int * array_list,int array_length); 
  15.  
  16. void Print(Tree* root); 
  17.  
  18. /***************************************************************/ 
  19. int Minimum(Tree * p); 
  20. Tree * TreeMinimum(Tree * root); 
  21. int Maximum(Tree * p); 
  22. Tree * TreeMaximum(Tree * root); 
  23. Tree * FindNode(Tree * root,int node_value); 
  24. Tree * Successor(Tree * root); 
  25. Tree * PredeSuccessor(Tree * p); 
  26. bool DeleteTreeNode(Tree * root,int node_value); 
  27. bool DeleteTreeNode(Tree * n); 
  28. /***************************************************************/ 
  29. int main(int argc,char * argv[]) 
  30.      
  31.     //int list[]={5,3,4,9,1,7,11};  
  32.     int list[]={15,5,16,3,12,20,10,13,18,23,6,7}; 
  33.     root = CreateBSTree(list,12); 
  34.     std::cout<<"Cearte BSTree."<<std::endl; 
  35.     //Print(root);  
  36.     //std::cout<<Successor(FindNode(root,4))->node_value;  
  37.     //Print(root);  
  38.     //std::cout<<std::endl;  
  39.     //DeleteTreeNode(root,15);  
  40.     //Print(root);  
  41.     Tree * t = FindNode(root,18); 
  42.     std::cout<<PredeSuccessor(t)->node_value; 
  43.     getchar(); 
  44.     return 0; 
  45. /*找出樹中的最小節點 
  46. p數的根節點 
  47. */ 
  48. int Minimum(Tree * p) 
  49.     Tree * t = TreeMinimum(p); 
  50.     if(t != NULL) 
  51.     { 
  52.         return t->node_value ; 
  53.     } 
  54.     else 
  55.     { 
  56.         return -1; 
  57.     } 
  58. Tree * TreeMinimum(Tree * p) 
  59.     if(p->left == NULL) 
  60.     { 
  61.         return p; 
  62.     } 
  63.     TreeMinimum(p->left); 
  64. /*找出樹中的最大節點*/ 
  65. int Maximum(Tree * p) 
  66.     Tree * t = TreeMaximum(root); 
  67.     if(t != NULL) 
  68.     { 
  69.         return t->node_value ; 
  70.     } 
  71.     else 
  72.     { 
  73.         return -1; 
  74.     } 
  75. Tree * TreeMaximum(Tree * p) 
  76.     if(p->right == NULL) 
  77.     { 
  78.         return p; 
  79.     } 
  80.     TreeMaximum(p->right); 
  81. /*假定所有的節點值都不相同,找到一個節點的指針 
  82. p樹的根節點, 
  83. node_value要查找的節點的值 
  84. */ 
  85. Tree * FindNode(Tree * p,int node_value) 
  86.     if(p == NULL) 
  87.     { 
  88.         return NULL;/*遞歸返回標志*/ 
  89.     } 
  90.     if(p->node_value == node_value) 
  91.     { 
  92.         return p; 
  93.     } 
  94.     if(p->node_value < node_value) 
  95.     { 
  96.         FindNode(p->right, node_value); 
  97.     } 
  98.     else 
  99.     { 
  100.         FindNode(p->left, node_value); 
  101.     } 
  102.      
  103. /*找出一個節點的後繼結點*/ 
  104. Tree * Successor(Tree * p) 
  105.     if(p == NULL) 
  106.     { 
  107.         return NULL; 
  108.     } 
  109.     if(p->right != NULL) 
  110.     { 
  111.         return TreeMinimum(p->right); 
  112.     } 
  113.     Tree * t = p->parent ; 
  114.     while((t != NULL) && (p == t->right)) 
  115.     { 
  116.         p = t; 
  117.         t = t->parent ; 
  118.     } 
  119.     return t; 
  120. /*找到一個節點的前驅節點 
  121. p為節點的指針 
  122. */ 
  123. Tree * PredeSuccessor(Tree * p) 
  124.     if(p == NULL) 
  125.     { 
  126.         return NULL; 
  127.     } 
  128.     else if(p->left != NULL) 
  129.     {/*如果左子樹不為空,則前驅為其左子樹的最大值節點*/ 
  130.         return TreeMaximum(p->left); 
  131.     } 
  132.     else 
  133.     { 
  134.         Tree * t = p->parent ; 
  135.         while((t != NULL) && (p == t->left)) 
  136.         {/*注意節點t的方向,這個與尋找後繼節點相反*/ 
  137.             p = t; 
  138.             t = t->parent; 
  139.         } 
  140.         return t; 
  141.     } 
  142. /*刪除一個節點 
  143. p為樹根節點指針 
  144. node_value要刪除的節點的值 
  145. */ 
  146. bool DeleteTreeNode(Tree * p,int node_value) 
  147.     Tree * t = FindNode(p,node_value); 
  148.     if(t == NULL) 
  149.     { 
  150.         return false
  151.     } 
  152.     if((t->left == NULL)&&(t->right == NULL)) 
  153.     {/*沒有子節點*/ 
  154.         Tree* tmp = t; 
  155.         if(tmp->parent->left == tmp) 
  156.         { 
  157.             tmp->parent->left = NULL; 
  158.         } 
  159.         else 
  160.         { 
  161.             tmp->parent->right = NULL; 
  162.         } 
  163.         delete tmp; 
  164.         tmp = NULL; 
  165.     } 
  166.     else if((t->left == NULL)||(t->right == NULL)) 
  167.     {/*一個子節點*/ 
  168.         Tree* tmp = t; 
  169.         if(tmp->parent->left == tmp) 
  170.         { 
  171.             tmp->parent->left = (tmp->left ==NULL)?tmp->right :tmp->left; 
  172.         } 
  173.         else 
  174.         { 
  175.             tmp->parent->right = (tmp->left ==NULL)?tmp->right :tmp->left; 
  176.         } 
  177.         delete tmp; 
  178.         tmp = NULL; 
  179.     } 
  180.     else 
  181.     {/*兩個子節點*/ 
  182.         Tree* s = Successor(t); 
  183.         if(s == NULL) 
  184.         { 
  185.             return false
  186.         } 
  187.         t->node_value = s->node_value ; 
  188.         DeleteTreeNode(s); 
  189.  
  190.     } 
  191. /*刪除一個節點 
  192. p為樹根節點指針 
  193. */ 
  194. bool DeleteTreeNode(Tree * n) 
  195.     if(n == NULL) 
  196.     { 
  197.         return NULL; 
  198.     } 
  199.     else if((n->left == NULL)&&(n->right == NULL)) 
  200.     {/*沒有子節點*/ 
  201.         Tree* tmp = n; 
  202.         if(tmp->parent->left == tmp) 
  203.         { 
  204.             tmp->parent->left = NULL; 
  205.         } 
  206.         else 
  207.         { 
  208.             tmp->parent->right = NULL; 
  209.         } 
  210.         delete tmp; 
  211.         tmp = NULL; 
  212.     } 
  213.     else if((n->left == NULL)||(n->right == NULL)) 
  214.     {/*一個子節點*/ 
  215.         Tree* tmp = n; 
  216.         if(tmp->parent->left == tmp) 
  217.         { 
  218.             tmp->parent->left = (tmp->left ==NULL)?tmp->right :tmp->left; 
  219.         } 
  220.         else 
  221.         { 
  222.             tmp->parent->right = (tmp->left ==NULL)?tmp->right :tmp->left; 
  223.         } 
  224.         delete tmp; 
  225.         tmp = NULL; 
  226.     } 
  227.     else 
  228.     {/*兩個子節點*/ 
  229.         Tree* s = Successor(n); 
  230.         if(s == NULL) 
  231.         { 
  232.             return false
  233.         } 
  234.         n->node_value = s->node_value ; 
  235.         DeleteTreeNode(s); 
  236.  
  237.     } 
  238. /*生成二叉查找樹*/ 
  239. Tree * CreateBSTree(int * array_list,int array_length) 
  240.     if(array_length <= 0) 
  241.     { 
  242.         return false
  243.     } 
  244.     Tree * root = NULL; 
  245.     root = new BSTree(); 
  246.     root->left = NULL; 
  247.     root->right = NULL; 
  248.     root->parent = NULL; 
  249.     root->node_value = array_list[0]; 
  250.     for(int i=1;i<array_length;i++) 
  251.     { 
  252.         CreateBSTree(root,array_list[i]); 
  253.     } 
  254.     return root; 
  255. void  CreateBSTree(Tree * root,int node_value) 
  256.     if(root == NULL) 
  257.     { 
  258.         return ; 
  259.     } 
  260.     if(root->node_value > node_value) 
  261.     { 
  262.         if(root->left == NULL) 
  263.         { 
  264.             Tree * node = new Tree(); 
  265.             node->left = NULL; 
  266.             node->right = NULL; 
  267.             node->node_value = node_value; 
  268.             node->parent = root; 
  269.             root->left = node; 
  270.  
  271.         } 
  272.         else 
  273.         { 
  274.              CreateBSTree(root->left,node_value); 
  275.         } 
  276.     } 
  277.     else 
  278.     { 
  279.         if(root->right == NULL) 
  280.         { 
  281.             Tree * node = new Tree(); 
  282.             node->left = NULL; 
  283.             node->right = NULL; 
  284.             node->node_value = node_value; 
  285.             node->parent = root; 
  286.             root->right = node; 
  287.         } 
  288.         else 
  289.         { 
  290.              CreateBSTree(root->right,node_value); 
  291.         } 
  292.     } 
  293. /*中序排序輸出二叉查找樹*/ 
  294. void Print(Tree* root) 
  295.     if(root == NULL) 
  296.     { 
  297.         return ; 
  298.     } 
  299.     Print(root->left); 
  300.     std::cout<<root->node_value<<"\t"; 
  301.     Print(root->right); 
Copyright © Linux教程網 All Rights Reserved