计算机视觉
图像处理

【数据结构】二叉树、AVL树

文章目录

二叉树

二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。

二叉树有几点重要的性质:

  •  性质1:在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1)
  • 性质2:深度为 k 的二叉树上至多含2k-1 个结点(k≥1)。
  • 性质3:对任何一棵二叉树,若它含有n0 个叶子结点、n2 个度为 2 的结点,则必存在关系式:n0 = n2+1。
  • 性质4:具有 n 个结点的完全二叉树的深度为log2n+1
  • 性质5:若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号,则对完全二叉树中任意一个编号为 i 的结点:
    (1) 若 i=1,则该结点是二叉树的根,无双亲,否则,编号为i/2 的结点为其双亲结点;
    (2) 若 2i>n,则该结点无左孩子,否则,编号为 2i 的结点为其左孩子结点;
    (3) 若 2i+1>n,则该结点无右孩子结点,否则,编号为2i+1 的结点为其右孩子结点。

采用链式存储结构实现二叉树

链式存储二叉树

1.首先我们要构造可以表示二叉树的节点的结构 Binary_node

2.构造类二叉树 Binary_tree,并编写其几个基本的成员函数:

Empty()-检查树是否为空;clear()-将树清空;size()-得到树的大小;leaf_count()-得到叶子数目;height()-得到树高;

以及几个重要的成员函数:

  1. Binary_tree(const Binary_tree<Entry>&original); 拷贝构造成员函数
  2. Binary_tree &operator=(const Binary_tree<Entry>&original);重载赋值操作符
  3. ~Binary_tree();析构函数

 

3.分别编写遍历算法的成员函数

  1. void inorder(void(*visit)(Entry &)); 中序遍历(LVR)
  2. void preorder(void(*visit)(Entry &)); 前序遍历(VLR)
  3. void postorder(void(*visit)(Entry &)); 后续遍历(LRV)

因为二叉树的性质,三种遍历算法我们都用递归实现,所以分别编写其递归函数

  1. void recursive_inorder(Binary_node<Entry>*sub_root,void (*visit)(Entry &));
  2. void recursive_preorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &));
  3. void recursive_postorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &));

 

4.作为辅助,我们再编写一个print_tree的函数,用以以括号表示法输出
同样使用递归,编写递归函数void recursive_print(Binary_node<Entry>*sub_root);
几个重要的函数代码如下:

  1. template<class Entry>
  2. void Binary_tree<Entry>::inorder(void(*visit)(Entry &))
  3. //Post: The tree has been traversed in inorder sequence
  4. //Uses: The function recursive_inorder
  5. {
  6.     recursive_inorder(root,visit);
  7. }
  8. template<class Entry>
  9. void Binary_tree<Entry>::recursive_inorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &))
  10. //Pre:  sub_root is either NULL or points to a subtree of the Binary_tree
  11. //Post: The subtree has been traversed in inorder sequence
  12. //Uses: The function recursive_inorder recursively
  13. {
  14.     if(sub_root!=NULL){
  15.         recursive_inorder(sub_root->left,visit);
  16.         (*visit)(sub_root->data);
  17.         recursive_inorder(sub_root->right,visit);
  18.     }
  19. }
  20. template<class Entry>
  21. void Binary_tree<Entry>::preorder(void(*visit)(Entry &))
  22. //Post: The tree has been traversed in preorder sequence
  23. //Uses: The function recursive_preorder
  24. {
  25.     recursive_preorder(root,visit);
  26. }
  27. template<class Entry>
  28. void Binary_tree<Entry>::recursive_preorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &))
  29. //Pre:  sub_root is either NULL or points to a subtree of the Binary_tree
  30. //Post: The subtree has been traversed in preorder sequence
  31. //Uses: The function recursive_preorder recursively
  32. {
  33.     if(sub_root!=NULL){
  34.         (*visit)(sub_root->data);
  35.         recursive_preorder(sub_root->left,visit);
  36.         recursive_preorder(sub_root->right,visit);
  37.     }
  38. }
  39. template<class Entry>
  40. void Binary_tree<Entry>::postorder(void(*visit)(Entry &))
  41. //Post: The tree has been traversed in postorder sequence
  42. //Uses: The function recursive_postorder
  43. {
  44.     recursive_postorder(root,visit);
  45. }
  46. template<class Entry>
  47. void Binary_tree<Entry>::recursive_postorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &))
  48. //Pre:  sub_root is either NULL or points to a subtree fo the Binary_tree
  49. //Post: The subtree has been traversed in postorder sequence
  50. //Uses: The function recursive_postorder recursively
  51. {
  52.     if(sub_root!=NULL){
  53.         recursive_postorder(sub_root->left,visit);
  54.         recursive_postorder(sub_root->right,visit);
  55.         (*visit)(sub_root->data);
  56.     }
  57. }
  58. template<class Entry>
  59. void Binary_tree<Entry>::print_tree()
  60. {
  61.     recursive_print(root);
  62.     cout<<endl;
  63. }
  64. template<class Entry>
  65. void Binary_tree<Entry>::recursive_print(Binary_node<Entry>*sub_root)
  66. {
  67.     if(sub_root!=NULL){
  68.         cout<<sub_root->data;
  69.         cout<<“(“;
  70.         recursive_print(sub_root->left);
  71.         cout<<“,”;
  72.         recursive_print(sub_root->right);
  73.         cout<<“)”;
  74.     }
  75. }
  76. //其他函数见源码

程序结果

插入二叉树并实现中序、前序和后序遍历

 

AVL树

AVL 树得名于其发明者G.M.Adelson-Velsky和E.M.Landis。AVL树是一个各结点具有平衡高度的扩展的二叉搜索树。在AVL树中,任 一结点的两个子树的高度差最多为1,AVL树的高度不会超过1,AVL树既有二叉搜索树的搜索效率又可以避免二叉搜索树的最坏情况(退化树)出现。

AVL树的表示与二叉搜索树类似,其操作基本相同,但插入和删除方法除外,因为它们必须不断监控结点的左右子树的相对高度,这也正是AVL树的优势所在。

实现AVL树的相关运算

1、首先我们修改结构Binary_node,增加Balance_factor用以表示节点平衡情况

2、从二叉搜索树中派生出AVL树,编写其关键的插入和删除成员函数。

  1. Error_code insert(const Record &new_data);
  2. Error_code remove(const Record &old_data);

3、入和删除函数我们都用递归实现
编写递归函数:

  1. Error_code avl_insert(Binary_node<Record>* &sub_root,
  2.                        const Record &new_data,bool &taller);
  3. Error_code avl_remove(Binary_node<Record>* &sub_root,
  4.                        const Record &target,bool &shorter);

以及几个重要的调用函数:
左旋右旋函数:

  1. void rotate_left(Binary_node<Record>* &sub_root);
  2. void rotate_right(Binary_node<Record>* &sub_root);

两次旋转的左右平衡函数

  1. void right_balance(Binary_node<Record>* &sub_root);
  2. void left_balance(Binary_node<Record>* &sub_root);

删除函数还要分别编写删除左树和删除右树的递归函数

  1. Error_code avl_remove_right(Binary_node<Record>&sub_root,
  2.                             const Record &target,bool &shorter);
  3. Error_code avl_remove_left(Binary_node<Record>*&sub_root,
  4.                             const Record &target,bool &shorter);

 

4、个重要的成员函数代码如下:

  1. template<class Record>
  2. Error_code AVL_tree<Record>::insert(const Record &new_data)
  3. //Post: If the key of new_data is already in the AVL_tree, a code of duplicate_error
  4. //      is returned. Otherwise, a code of success is returned and the Record
  5. //      new_data is inserted into the tree in such a way that the properties of an
  6. //      AVL tree are preserved.
  7. {
  8.     bool taller;
  9.     return avl_insert(root,new_data,taller);
  10. }
  11. template<class Record>
  12. Error_code AVL_tree<Record>::avl_insert(Binary_node<Record>* &sub_root, const Record &new_data,bool &taller)
  13. //Pre:  sub_root is either NULL or points to a subtree of the AVL tree
  14. //Post: If the key of new_data is already in the subtree, a code of duplicate_error
  15. //      is returned. Otherwise, a code of success is returned and the Record 
  16. //      new_data is inserted into the subtree in such a way that the properties of 
  17. //      an AVL tree have been preserved. If the subtree is increase in height, the
  18. //      parameter taller is set to true; otherwise it is set to false
  19. //Uses: Methods of struct AVL_node; functions avl_insert recursively, left_balance, and right_balance
  20. {
  21.     Error_code result=success;
  22.     if(sub_root==NULL){
  23.         sub_root=new Binary_node<Record>(new_data);
  24.         taller=true;
  25.     }
  26.     else if(new_data==sub_root->data){
  27.         result=duplicate_error;
  28.         taller=false;
  29.     }
  30.     else if(new_data<sub_root->data){//Insert in left subtree
  31.         result=avl_insert(sub_root->left,new_data,taller);
  32.         if(taller==true)
  33.             switch(sub_root->get_balance()){//Change balance factors
  34.             case left_higher:
  35.                 left_balance(sub_root);
  36.                 taller=false;
  37.                 break;
  38.             case equal_height:
  39.                 sub_root->set_balance(left_higher);
  40.                 break;
  41.             case right_higher:
  42.                 sub_root->set_balance(equal_height);
  43.                 taller=false;
  44.                 break;
  45.         }
  46.     }
  47.     else{        //Insert in right subtree
  48.         result=avl_insert(sub_root->right,new_data,taller);
  49.         if(taller==true)
  50.             switch(sub_root->get_balance()){
  51.             case left_higher:
  52.                 sub_root->set_balance(equal_height);
  53.                 taller=false;
  54.                 break;
  55.             case equal_height:
  56.                 sub_root->set_balance(right_higher);
  57.                 break;
  58.             case right_higher:
  59.                 right_balance(sub_root);
  60.                 taller=false//Rebalancing always shortens the tree
  61.                 break;
  62.         }
  63.     }
  64.     return result;
  65. }
  66. template<class Record>
  67. void AVL_tree<Record>::right_balance(Binary_node<Record>* &sub_root)
  68. //Pre:  sub_root points to a subtree of an AVL_tree that is doubly unbalanced
  69. //      on the right
  70. //Post: The AVL properties have been restored to the subtree
  71. {
  72.     Binary_node<Record>* &right_tree=sub_root->right;
  73.     switch(right_tree->get_balance()){
  74.     case right_higher:
  75.         sub_root->set_balance(equal_height);
  76.         right_tree->set_balance(equal_height);
  77.         rotate_left(sub_root);
  78.         break;
  79.     case equal_height:
  80.         cout<<“WARNING: program error detected in right_balance “<<endl;
  81.     case left_higher:
  82.         Binary_node<Record>*sub_tree=right_tree->left;
  83.         switch(sub_tree->get_balance()){
  84.         case equal_height:
  85.             sub_root->set_balance(equal_height);
  86.             right_tree->set_balance(equal_height);
  87.             break;
  88.         case left_higher:
  89.             sub_root->set_balance(equal_height);
  90.             right_tree->set_balance(right_higher);
  91.         case right_higher:
  92.             sub_root->set_balance(left_higher);
  93.             right_tree->set_balance(equal_height);
  94.             break;
  95.         }
  96.         sub_tree->set_balance(equal_height);
  97.         rotate_right(right_tree);
  98.         rotate_left(sub_root);
  99.         break;
  100.     }
  101. }
  102. template<class Record>
  103. void AVL_tree<Record>::left_balance(Binary_node<Record>* &sub_root)
  104. {
  105.     Binary_node<Record>* &left_tree=sub_root->left;
  106.     switch(left_tree->get_balance()){
  107.     case left_higher:
  108.         sub_root->set_balance(equal_height);
  109.         left_tree->set_balance(equal_height);
  110.         rotate_right(sub_root);
  111.         break;
  112.     case equal_height:
  113.         cout<<“WARNING: program error detected in left_balance”<<endl;
  114.     case right_higher:
  115.         Binary_node<Record>*sub_tree=left_tree->right;
  116.         switch(sub_tree->get_balance()){
  117.         case equal_height:
  118.             sub_root->set_balance(equal_height);
  119.             left_tree->set_balance(equal_height);
  120.             break;
  121.         case right_higher:
  122.             sub_root->set_balance(equal_height);
  123.             left_tree->set_balance(left_higher);
  124.             break;
  125.         case left_higher:
  126.             sub_root->set_balance(right_higher);
  127.             left_tree->set_balance(equal_height);
  128.             break;
  129.         }
  130.         sub_tree->set_balance(equal_height);
  131.         rotate_left(left_tree);
  132.         rotate_right(sub_root);
  133.         break;
  134.     }
  135. }
  136. template<class Record>
  137. void AVL_tree<Record>::rotate_left(Binary_node<Record>* &sub_root)
  138. //Pre:  sub_root points to a subtree of the AVL_tree. This subtree has 
  139. //      a nonempty right subtree.
  140. //Post: sub_root is reset to point to its former right child, and the 
  141. //      former sub_root node is the left child of the new sub_root node
  142. {
  143.     if(sub_root==NULL||sub_root->right==NULL)//impossible cases
  144.         cout<<“WARNING: program error detected in rotate_left”<<endl;
  145.     else{
  146.         Binary_node<Record>*right_tree=sub_root->right;
  147.         sub_root->right=right_tree->left;
  148.         right_tree->left=sub_root;
  149.         sub_root=right_tree;
  150.     }
  151. }
  152. template<class Record>
  153. void AVL_tree<Record>::rotate_right(Binary_node<Record>*&sub_root)
  154. {
  155.     if(sub_root==NULL||sub_root->left==NULL)
  156.         cout<<“WARNING:program error in detected in rotate_right”<<endl;
  157.     else{
  158.         Binary_node<Record>*left_tree=sub_root->left;
  159.         sub_root->left=left_tree->right;
  160.         left_tree->right=sub_root;
  161.         sub_root=left_tree;
  162.     }
  163. }
  164. template<class Record>
  165. Error_code AVL_tree<Record>::remove(const Record &old_data)
  166. {
  167.     bool shorter;
  168.     return avl_remove(root,old_data,shorter);
  169. }
  170. template<class Record>
  171. Error_code AVL_tree<Record>::avl_remove(Binary_node<Record>* &sub_root,
  172.                                         const Record &target,bool &shorter)
  173. {
  174.     Binary_node<Record>*temp;
  175.     if(sub_root==NULL)return fail;
  176.     else if(target<sub_root->data)
  177.         return avl_remove_left(sub_root,target,shorter);
  178.     else if(target>sub_root->data)
  179.         return avl_remove_right(sub_root,target,shorter);
  180.     else if(sub_root->left==NULL){//Found target: delete current node
  181.         temp=sub_root;       //Move right subtree up to delete node
  182.         sub_root=sub_root->right;
  183.         delete temp;
  184.         shorter=true;
  185.     }
  186.     else if(sub_root->right==NULL){
  187.         temp=sub_root;   //Move left subtree up to delete node
  188.         sub_root=sub_root->left;
  189.         delete temp;
  190.         shorter=true;
  191.     }
  192.     else if(sub_root->get_balance()==left_higher){
  193.         //Neither subtree is empty; delete from the taller
  194.         temp=sub_root->left;//Find predecessor of target and delete if from left tree
  195.         while(temp->right!=NULL)temp=temp->right;
  196.         sub_root->data=temp->data;
  197.         avl_remove_left(sub_root,temp->data,shorter);
  198.     }
  199.     else{
  200.         temp=sub_root->right;
  201.         while(temp->left!=NULL)temp=temp->left;
  202.         sub_root->data=temp->data;
  203.         avl_remove_right(sub_root,temp->data,shorter);
  204.     }
  205.     return success;
  206. }
  207. template<class Record>
  208. Error_code AVL_tree<Record>::avl_remove_right(Binary_node<Record>
  209.            *&sub_root,const Record &target,bool &shorter)
  210. {
  211.     Error_code result=avl_remove(sub_root->right,target,shorter);
  212.     if(shorter==true)switch(sub_root->get_balance()){
  213.         case equal_height:
  214.             sub_root->set_balance(left_higher);
  215.             shorter=false;
  216.             break;
  217.         case right_higher:
  218.             sub_root->set_balance(equal_height);
  219.             break;
  220.         case left_higher:
  221.             Binary_node<Record>*temp=sub_root->left;
  222.             switch(temp->get_balance()){
  223.             case equal_height:
  224.                 temp->set_balance(right_higher);
  225.                 rotate_right(sub_root);
  226.                 shorter=false;
  227.                 break;
  228.             case left_higher:
  229.                 sub_root->set_balance(equal_height);
  230.                 temp->set_balance(equal_height);
  231.                 rotate_right(sub_root);
  232.                 break;
  233.             case right_higher:
  234.                 Binary_node<Record>*temp_right=temp->right;
  235.                 switch(temp_right->get_balance()){
  236.                 case equal_height:
  237.                     sub_root->set_balance(equal_height);
  238.                     temp->set_balance(equal_height);
  239.                     break;
  240.                 case left_higher:
  241.                     sub_root->set_balance(right_higher);
  242.                     temp->set_balance(equal_height);
  243.                     break;
  244.                 case right_higher:
  245.                     sub_root->set_balance(equal_height);
  246.                     temp->set_balance(left_higher);
  247.                     break;
  248.                 }
  249.                 temp_right->set_balance(equal_height);
  250.                 rotate_left(sub_root->left);
  251.                 rotate_right(sub_root);
  252.                 break;
  253.             }
  254.     }
  255.     return result;
  256. }
  257. template<class Record>
  258. Error_code AVL_tree<Record>::avl_remove_left(Binary_node<Record>
  259.            *&sub_root,const Record &target,bool &shorter)
  260. {
  261.     Error_code result=avl_remove(sub_root->left,target,shorter);
  262.     if(shorter==true)
  263.         switch(sub_root->get_balance()){
  264.         case equal_height:
  265.             sub_root->set_balance(right_higher);
  266.             shorter=false;
  267.             break;
  268.         case left_higher:
  269.             sub_root->set_balance(equal_height);
  270.             break;
  271.         case right_higher:
  272.             Binary_node<Record>*temp=sub_root->right;
  273.             switch(temp->get_balance()){
  274.             case equal_height:
  275.                 temp->set_balance(left_higher);
  276.                 rotate_right(sub_root);
  277.                 shorter=false;
  278.                 break;
  279.             case right_higher:
  280.                 sub_root->set_balance(equal_height);
  281.                 temp->set_balance(equal_height);
  282.                 rotate_left(sub_root);
  283.                 break;
  284.             case left_higher:
  285.                 Binary_node<Record>*temp_left=temp->left;
  286.                 switch(temp_left->get_balance()){
  287.                 case equal_height:
  288.                     sub_root->set_balance(equal_height);
  289.                     temp->set_balance(equal_height);
  290.                     break;
  291.                 case right_higher:
  292.                     sub_root->set_balance(left_higher);
  293.                     temp->set_balance(equal_height);
  294.                     break;
  295.                 case left_higher:
  296.                     sub_root->set_balance(equal_height);
  297.                     temp->set_balance(right_higher);
  298.                     break;
  299.                 }
  300.                 temp_left->set_balance(equal_height);
  301.                 rotate_right(sub_root->right);
  302.                 rotate_left(sub_root);
  303.                 break;
  304.             }
  305.     }
  306.     return result;
  307. }

实验结果

实现如下功能:1)由{4,9,0,1,8,6,3,5,2,7}建AVL树B,并以括号表示法输出;2)删除B中关键字为8和2的结点,输出结果。

 

分析总结

 

采用链式存储结构实现二叉树

  1. 二 叉树在插入的时候通过判断待插入数据与根节点数据的大小,若小于根数据,插入左树,反之插入右树(我们规定不许有重复元素);二叉树的存储结构常用于搜索 等。但搜索的效率常依赖于树的结构。而树的结构与元素插入顺序有很大关系,用上述方法插入时若插入的元素是有序的,则得到的树与队列几乎没有区别,也起不 到优化搜索的目的。
  2. 二叉树的遍历算法最为重要的一点是递归,递归使我们不必关心于具体的遍历每个节点的顺序,而只是将其看做三个部分,即左子树,根节点,右子树,具体子树的遍历仍是调用其递归函数。
    3.在打印树的时候,我写的并不完美,因为对于叶子节点,理想应该不再打印括号,但我通过判断根节点不为空而调用递归函数,即只要节点有元素就会输出(,),还是表达出了树的意思,但并没有想到怎样达到简洁的效果。

实现AVL树的相关运算

  1. AVL树每插入,删除一个节点就会判断树的高度并改变相应节点的平衡因素,每当有节点不再满足AVL树的性质,立即通过旋转得到AVL树
  2. 旋转的函数及其巧妙。而插入和删除元素的函数要考虑的情况非常多,一种情况没有考虑到就可能达不到我们想要的效果,函数的编写需要极大的耐心和对编程语句的熟练掌握。很多地方我是参考书上的,别人的代码我可以理解,但我自己写可能还是会漏掉很多情况。

转载注明来源:CV视觉网 » 【数据结构】二叉树、AVL树

分享到:更多 ()
扫描二维码,给作者 打赏
pay_weixinpay_weixin

请选择你看完该文章的感受:

0不错 0超赞 0无聊 0扯淡 0不解 0路过

评论 3

评论前必须登录!