Welcome 微信登录
编程资源 图片资源库 蚂蚁家优选 PDF转换器 软件资源

软件开发、小程序制作、系统集成与运维、空间租用、硬件开发、视频监控、技术咨询与支持——联系电话：0311-88999002/88999003

首页 / 操作系统 / Linux / 【算法导论】二叉查找树的操作C++实现

本代码为算法导论第12章中，伪代码的C++实现：
  1. #include <iostream>  
  2. #include <vector>  
  3. using namespace std; 
  4. /*二叉查找树结构*/ 
  5. typedef struct BSTree 
  6. { 
  7.     int node_value; 
  8.     struct BSTree * left; 
  9.     struct BSTree * right; 
  10.     struct BSTree * parent; 
  11. }Tree; 
  12. Tree * root = NULL; 
  13. /*****构造二叉查找树**********************************************/ 
  14. void  CreateBSTree（Tree * root,int node_value）; 
  15. Tree * CreateBSTree（int * array_list,int array_length）; 
  16.  
  17. void Print（Tree* root）; 
  18.  
  19. /***************************************************************/ 
  20. int Minimum（Tree * p）; 
  21. Tree * TreeMinimum（Tree * root）; 
  22. int Maximum（Tree * p）; 
  23. Tree * TreeMaximum（Tree * root）; 
  24. Tree * FindNode（Tree * root,int node_value）; 
  25. Tree * Successor（Tree * root）; 
  26. Tree * PredeSuccessor（Tree * p）; 
  27. bool DeleteTreeNode（Tree * root,int node_value）; 
  28. bool DeleteTreeNode（Tree * n）; 
  29. /***************************************************************/ 
  30. int main（int argc,char * argv[]） 
  31. { 
  32.      
  33.     //int list[]={5,3,4,9,1,7,11};  
  34.     int list[]={15,5,16,3,12,20,10,13,18,23,6,7}; 
  35.     root = CreateBSTree（list,12）; 
  36.     std::cout<<"Cearte BSTree."<<std::endl; 
  37.     //Print（root）;  
  38.     //std::cout<<Successor（FindNode（root,4））->node_value;  
  39.     //Print（root）;  
  40.     //std::cout<<std::endl;  
  41.     //DeleteTreeNode（root,15）;  
  42.     //Print（root）;  
  43.     Tree * t = FindNode（root,18）; 
  44.     std::cout<<PredeSuccessor（t）->node_value; 
  45.     getchar（）; 
  46.     return 0; 
  47. } 
  48. /*找出树中的最小节点 
  49. p数的根节点 
  50. */ 
  51. int Minimum（Tree * p） 
  52. { 
  53.     Tree * t = TreeMinimum（p）; 
  54.     if（t ！= NULL） 
  55.     { 
  56.         return t->node_value ; 
  57.     } 
  58.     else 
  59.     { 
  60.         return -1; 
  61.     } 
  62. } 
  63. Tree * TreeMinimum（Tree * p） 
  64. { 
  65.     if（p->left == NULL） 
  66.     { 
  67.         return p; 
  68.     } 
  69.     TreeMinimum（p->left）; 
  70. } 
  71. /*找出树中的最大节点*/ 
  72. int Maximum（Tree * p） 
  73. { 
  74.     Tree * t = TreeMaximum（root）; 
  75.     if（t ！= NULL） 
  76.     { 
  77.         return t->node_value ; 
  78.     } 
  79.     else 
  80.     { 
  81.         return -1; 
  82.     } 
  83. } 
  84. Tree * TreeMaximum（Tree * p） 
  85. { 
  86.     if（p->right == NULL） 
  87.     { 
  88.         return p; 
  89.     } 
  90.     TreeMaximum（p->right）; 
  91. } 
  92. /*假定所有的节点值都不相同，找到一个节点的指针 
  93. p树的根节点， 
  94. node_value要查找的节点的值 
  95. */ 
  96. Tree * FindNode（Tree * p,int node_value） 
  97. { 
  98.     if（p == NULL） 
  99.     { 
  100.         return NULL;/*递归返回标志*/ 
  101.     } 
  102.     if（p->node_value == node_value） 
  103.     { 
  104.         return p; 
  105.     } 
  106.     if（p->node_value < node_value） 
  107.     { 
  108.         FindNode（p->right, node_value）; 
  109.     } 
  110.     else 
  111.     { 
  112.         FindNode（p->left, node_value）; 
  113.     } 
  114.      
  115. } 
  116. /*找出一个节点的后继结点*/ 
  117. Tree * Successor（Tree * p） 
  118. { 
  119.     if（p == NULL） 
  120.     { 
  121.         return NULL; 
  122.     } 
  123.     if（p->right ！= NULL） 
  124.     { 
  125.         return TreeMinimum（p->right）; 
  126.     } 
  127.     Tree * t = p->parent ; 
  128.     while（（t ！= NULL） && （p == t->right）） 
  129.     { 
  130.         p = t; 
  131.         t = t->parent ; 
  132.     } 
  133.     return t; 
  134. } 
  135. /*找到一个节点的前驱节点 
  136. p为节点的指针 
  137. */ 
  138. Tree * PredeSuccessor（Tree * p） 
  139. { 
  140.     if（p == NULL） 
  141.     { 
  142.         return NULL; 
  143.     } 
  144.     else if（p->left ！= NULL） 
  145.     {/*如果左子树不为空，则前驱为其左子树的最大值节点*/ 
  146.         return TreeMaximum（p->left）; 
  147.     } 
  148.     else 
  149.     { 
  150.         Tree * t = p->parent ; 
  151.         while（（t ！= NULL） && （p == t->left）） 
  152.         {/*注意节点t的方向，这个与寻找后继节点相反*/ 
  153.             p = t; 
  154.             t = t->parent; 
  155.         } 
  156.         return t; 
  157.     } 
  158. } 
  159. /*删除一个节点 
  160. p为树根节点指针 
  161. node_value要删除的节点的值 
  162. */ 
  163. bool DeleteTreeNode（Tree * p,int node_value） 
  164. { 
  165.     Tree * t = FindNode（p,node_value）; 
  166.     if（t == NULL） 
  167.     { 
  168.         return false; 
  169.     } 
  170.     if（（t->left == NULL）&&（t->right == NULL）） 
  171.     {/*没有子节点*/ 
  172.         Tree* tmp = t; 
  173.         if（tmp->parent->left == tmp） 
  174.         { 
  175.             tmp->parent->left = NULL; 
  176.         } 
  177.         else 
  178.         { 
  179.             tmp->parent->right = NULL; 
  180.         } 
  181.         delete tmp; 
  182.         tmp = NULL; 
  183.     } 
  184.     else if（（t->left == NULL）||（t->right == NULL）） 
  185.     {/*一个子节点*/ 
  186.         Tree* tmp = t; 
  187.         if（tmp->parent->left == tmp） 
  188.         { 
  189.             tmp->parent->left = （tmp->left ==NULL）？tmp->right :tmp->left; 
  190.         } 
  191.         else 
  192.         { 
  193.             tmp->parent->right = （tmp->left ==NULL）？tmp->right :tmp->left; 
  194.         } 
  195.         delete tmp; 
  196.         tmp = NULL; 
  197.     } 
  198.     else 
  199.     {/*两个子节点*/ 
  200.         Tree* s = Successor（t）; 
  201.         if（s == NULL） 
  202.         { 
  203.             return false; 
  204.         } 
  205.         t->node_value = s->node_value ; 
  206.         DeleteTreeNode（s）; 
  207.  
  208.     } 
  209. } 
  210. /*删除一个节点 
  211. p为树根节点指针 
  212. */ 
  213. bool DeleteTreeNode（Tree * n） 
  214. { 
  215.     if（n == NULL） 
  216.     { 
  217.         return NULL; 
  218.     } 
  219.     else if（（n->left == NULL）&&（n->right == NULL）） 
  220.     {/*没有子节点*/ 
  221.         Tree* tmp = n; 
  222.         if（tmp->parent->left == tmp） 
  223.         { 
  224.             tmp->parent->left = NULL; 
  225.         } 
  226.         else 
  227.         { 
  228.             tmp->parent->right = NULL; 
  229.         } 
  230.         delete tmp; 
  231.         tmp = NULL; 
  232.     } 
  233.     else if（（n->left == NULL）||（n->right == NULL）） 
  234.     {/*一个子节点*/ 
  235.         Tree* tmp = n; 
  236.         if（tmp->parent->left == tmp） 
  237.         { 
  238.             tmp->parent->left = （tmp->left ==NULL）？tmp->right :tmp->left; 
  239.         } 
  240.         else 
  241.         { 
  242.             tmp->parent->right = （tmp->left ==NULL）？tmp->right :tmp->left; 
  243.         } 
  244.         delete tmp; 
  245.         tmp = NULL; 
  246.     } 
  247.     else 
  248.     {/*两个子节点*/ 
  249.         Tree* s = Successor（n）; 
  250.         if（s == NULL） 
  251.         { 
  252.             return false; 
  253.         } 
  254.         n->node_value = s->node_value ; 
  255.         DeleteTreeNode（s）; 
  256.  
  257.     } 
  258. } 
  259. /*生成二叉查找树*/ 
  260. Tree * CreateBSTree（int * array_list,int array_length） 
  261. { 
  262.     if（array_length <= 0） 
  263.     { 
  264.         return false; 
  265.     } 
  266.     Tree * root = NULL; 
  267.     root = new BSTree（）; 
  268.     root->left = NULL; 
  269.     root->right = NULL; 
  270.     root->parent = NULL; 
  271.     root->node_value = array_list[0]; 
  272.     for（int i=1;i<array_length;i++） 
  273.     { 
  274.         CreateBSTree（root,array_list[i]）; 
  275.     } 
  276.     return root; 
  277. } 
  278. void  CreateBSTree（Tree * root,int node_value） 
  279. { 
  280.     if（root == NULL） 
  281.     { 
  282.         return ; 
  283.     } 
  284.     if（root->node_value > node_value） 
  285.     { 
  286.         if（root->left == NULL） 
  287.         { 
  288.             Tree * node = new Tree（）; 
  289.             node->left = NULL; 
  290.             node->right = NULL; 
  291.             node->node_value = node_value; 
  292.             node->parent = root; 
  293.             root->left = node; 
  294.  
  295.         } 
  296.         else 
  297.         { 
  298.              CreateBSTree（root->left,node_value）; 
  299.         } 
  300.     } 
  301.     else 
  302.     { 
  303.         if（root->right == NULL） 
  304.         { 
  305.             Tree * node = new Tree（）; 
  306.             node->left = NULL; 
  307.             node->right = NULL; 
  308.             node->node_value = node_value; 
  309.             node->parent = root; 
  310.             root->right = node; 
  311.         } 
  312.         else 
  313.         { 
  314.              CreateBSTree（root->right,node_value）; 
  315.         } 
  316.     } 
  317. } 
  318. /*中序排序输出二叉查找树*/ 
  319. void Print（Tree* root） 
  320. { 
  321.     if（root == NULL） 
  322.     { 
  323.         return ; 
  324.     } 
  325.     Print（root->left）; 
  326.     std::cout<<root->node_value<<" "; 
  327.     Print（root->right）; 
  328. } 
版权所有©石家庄振强科技有限公司2024 冀ICP备08103738号-5 网站地图