加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 （https://www.lidatong.com.cn/）- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置： 首页 > 综合聚焦 > 服务器 > 安全 > 正文

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

发布时间：2020-12-15 06:08:48 所属栏目：安全 来源：网络整理
导读：二叉树 二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。 二叉树有几点重要的性质

二叉树

二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（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()-得到树高；

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

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

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

    voidinorder(void(*visit)(Entry&));中序遍历（LVR）
  1. voidpreorder(void(*visit)(Entry&));前序遍历（VLR）
  2. voidpostorder(void(*visit)(Entry&));后续遍历（LRV）

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

    voidrecursive_inorder(Binary_node<Entry>*sub_root,void(*visit)(Entry&));
  1. voidrecursive_preorder(Binary_node<Entry>*sub_root,153); background-color:inherit; font-weight:bold">void(*visit)(Entry&));
  2. voidrecursive_postorder(Binary_node<Entry>*sub_root,153); background-color:inherit; font-weight:bold">void(*visit)(Entry&));

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

    template<classEntry>
  1. voidBinary_tree<Entry>::inorder(void(*visit)(Entry&))
  2. //Post:Thetreehasbeentraversedininordersequence
  3. //Uses:Thefunctionrecursive_inorder
  4. {
  5. recursive_inorder(root,visit);
  6. }
  8. voidBinary_tree<Entry>::recursive_inorder(Binary_node<Entry>*sub_root,0); background-color:inherit">//Pre:sub_rootiseitherNULLorpointstoasubtreeoftheBinary_tree
  9. //Post:Thesubtreehasbeentraversedininordersequence
  10. //Uses:Thefunctionrecursive_inorderrecursively
  11. {
  12. if(sub_root!=NULL){
  13. recursive_inorder(sub_root->left,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> (*visit)(sub_root->data);
  14. recursive_inorder(sub_root->right,248); line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> }
  16. classEntry>
  17. voidBinary_tree<Entry>::preorder(void(*visit)(Entry&))
  18. //Post:Thetreehasbeentraversedinpreordersequence
  19. //Uses:Thefunctionrecursive_preorder
  20. recursive_preorder(root,visit);
  21. voidBinary_tree<Entry>::recursive_preorder(Binary_node<Entry>*sub_root,0); background-color:inherit">//Pre:sub_rootiseitherNULLorpointstoasubtreeoftheBinary_tree
  22. //Post:Thesubtreehasbeentraversedinpreordersequence
  23. //Uses:Thefunctionrecursive_preorderrecursively
  24. if(sub_root!=NULL){
  25. recursive_preorder(sub_root->left,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> recursive_preorder(sub_root->right,153); background-color:inherit; font-weight:bold">voidBinary_tree<Entry>::postorder(//Post:Thetreehasbeentraversedinpostordersequence
  26. //Uses:Thefunctionrecursive_postorder
  27. recursive_postorder(root,153); background-color:inherit; font-weight:bold">voidBinary_tree<Entry>::recursive_postorder(Binary_node<Entry>*sub_root,0); background-color:inherit">//Pre:sub_rootiseitherNULLorpointstoasubtreefotheBinary_tree
  28. //Post:Thesubtreehasbeentraversedinpostordersequence
  29. //Uses:Thefunctionrecursive_postorderrecursively
  30. recursive_postorder(sub_root->left,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> recursive_postorder(sub_root->right,248); line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> (*visit)(sub_root->data);
  31. voidBinary_tree<Entry>::print_tree()
  32. recursive_print(root);
  33. cout<<endl;
  34. voidBinary_tree<Entry>::recursive_print(Binary_node<Entry>*sub_root)
  35. cout<<sub_root->data;
  36. cout<<"(";
  37. recursive_print(sub_root->left);
  38. cout<<",";
  39. recursive_print(sub_root->right);
  40. cout<<")";
  41. //其他函数见源码


程序结果

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

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树，编写其关键的插入和删除成员函数。

    Error_codeinsert(constRecord&new_data);
  1. Error_coderemove(constRecord&old_data);

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

    Error_codeavl_insert(Binary_node<Record>*&sub_root,
  1. constRecord&new_data,bool&taller);
  2. Error_codeavl_remove(Binary_node<Record>*&sub_root,
  3. constRecord&target,87); background-color:inherit; font-weight:bold">bool&shorter);

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

    voidrotate_left(Binary_node<Record>*&sub_root);
  1. voidrotate_right(Binary_node<Record>*&sub_root);

两次旋转的左右平衡函数

    voidright_balance(Binary_node<Record>*&sub_root);
  1. voidleft_balance(Binary_node<Record>*&sub_root);

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

    Error_codeavl_remove_right(Binary_node<Record>&sub_root,87); background-color:inherit; font-weight:bold">bool&shorter);
  1. Error_codeavl_remove_left(Binary_node<Record>*&sub_root,51); font-family:Arial; font-size:14.399999618530273px; line-height:26px"> 4、个重要的成员函数代码如下：

      classRecord>
    1. Error_codeAVL_tree<Record>::insert(constRecord&new_data)
    2. //Post:Ifthekeyofnew_dataisalreadyintheAVL_tree,acodeofduplicate_error
    3. //isreturned.Otherwise,acodeofsuccessisreturnedandtheRecord
    4. //new_dataisinsertedintothetreeinsuchawaythatthepropertiesofan
    5. //AVLtreearepreserved.
    6. booltaller;
    7. returnavl_insert(root,new_data,taller);
    8. classRecord>
    9. Error_codeAVL_tree<Record>::avl_insert(Binary_node<Record>*&sub_root,bool&taller)
    10. //Pre:sub_rootiseitherNULLorpointstoasubtreeoftheAVLtree
    11. //Post:Ifthekeyofnew_dataisalreadyinthesubtree,0); background-color:inherit">//new_dataisinsertedintothesubtreeinsuchawaythatthepropertiesof
    12. //anAVLtreehavebeenpreserved.Ifthesubtreeisincreaseinheight,the
    13. //parametertallerissettotrue;otherwiseitissettofalse
    14. //Uses:MethodsofstructAVL_node;functionsavl_insertrecursively,left_balance,andright_balance
    15. Error_coderesult=success;
    16. if(sub_root==NULL){
    17. sub_root=newBinary_node<Record>(new_data);
    18. taller=true;
    19. elseif(new_data==sub_root->data){
    20. result=duplicate_error;
    21. false;
    22. if(new_data<sub_root->data){//Insertinleftsubtree
    23. result=avl_insert(sub_root->left,taller);
    24. if(taller==true)
    25. switch(sub_root->get_balance()){//Changebalancefactors
    26. caseleft_higher:
    27. left_balance(sub_root);
    28. break;
    29. caseequal_height:
    30. sub_root->set_balance(left_higher);
    31. break;
    32. caseright_higher:
    33. sub_root->set_balance(equal_height);
    34. taller=false;
    35. else{//Insertinrightsubtree
    36. result=avl_insert(sub_root->right,taller);
    37. true)
    38. switch(sub_root->get_balance()){
    39. caseleft_higher:
    40. caseequal_height:
    41. sub_root->set_balance(right_higher);
    42. caseright_higher:
    43. right_balance(sub_root);
    44. false;//Rebalancingalwaysshortensthetree
    45. returnresult;
    46. voidAVL_tree<Record>::right_balance(Binary_node<Record>*&sub_root)
    47. //Pre:sub_rootpointstoasubtreeofanAVL_treethatisdoublyunbalanced
    48. //ontheright
    49. //Post:TheAVLpropertieshavebeenrestoredtothesubtree
    50. Binary_node<Record>*&right_tree=sub_root->right;
    51. switch(right_tree->get_balance()){
    52. right_tree->set_balance(equal_height);
    53. rotate_left(sub_root);
    54. cout<<"WARNING:programerrordetectedinright_balance"<<endl;
    55. Binary_node<Record>*sub_tree=right_tree->left;
    56. switch(sub_tree->get_balance()){
    57. right_tree->set_balance(right_higher);
    58. right_tree->set_balance(equal_height);
    59. sub_tree->set_balance(equal_height);
    60. rotate_right(right_tree);
    61. rotate_left(sub_root);
    62. voidAVL_tree<Record>::left_balance(Binary_node<Record>*&sub_root)
    63. Binary_node<Record>*&left_tree=sub_root->left;
    64. switch(left_tree->get_balance()){
    65. left_tree->set_balance(equal_height);
    66. rotate_right(sub_root);
    67. cout<<"WARNING:programerrordetectedinleft_balance"<<endl;
    68. Binary_node<Record>*sub_tree=left_tree->right;
    69. left_tree->set_balance(left_higher);
    70. sub_tree->set_balance(equal_height);
    71. rotate_left(left_tree);
    72. voidAVL_tree<Record>::rotate_left(Binary_node<Record>*&sub_root)
    73. //Pre:sub_rootpointstoasubtreeoftheAVL_tree.Thissubtreehas
    74. //anonemptyrightsubtree.
    75. //Post:sub_rootisresettopointtoitsformerrightchild,andthe
    76. //formersub_rootnodeistheleftchildofthenewsub_rootnode
    77. if(sub_root==NULL||sub_root->right==NULL)//impossiblecases
    78. cout<<"WARNING:programerrordetectedinrotate_left"<<endl;
    79. else{
    80. Binary_node<Record>*right_tree=sub_root->right;
    81. sub_root->right=right_tree->left;
    82. right_tree->left=sub_root;
    83. sub_root=right_tree;
    84. voidAVL_tree<Record>::rotate_right(Binary_node<Record>*&sub_root)
    85. if(sub_root==NULL||sub_root->left==NULL)
    86. cout<<"WARNING:programerrorindetectedinrotate_right"<<endl;
    87. else{
    88. Binary_node<Record>*left_tree=sub_root->left;
    89. sub_root->left=left_tree->right;
    90. left_tree->right=sub_root;
    91. sub_root=left_tree;
    92. Error_codeAVL_tree<Record>::remove(constRecord&old_data)
    93. boolshorter;
    94. returnavl_remove(root,old_data,shorter);
    95. Error_codeAVL_tree<Record>::avl_remove(Binary_node<Record>*&sub_root,
    96. bool&shorter)
    97. Binary_node<Record>*temp;
    98. if(sub_root==NULL)returnfail;
    99. if(target<sub_root->data)
    100. returnavl_remove_left(sub_root,target,153); background-color:inherit; font-weight:bold">if(target>sub_root->data)
    101. returnavl_remove_right(sub_root,153); background-color:inherit; font-weight:bold">if(sub_root->left==NULL){//Foundtarget:deletecurrentnode
    102. temp=sub_root;//Moverightsubtreeuptodeletenode
    103. sub_root=sub_root->right;
    104. deletetemp;
    105. shorter=if(sub_root->right==NULL){
    106. //Moveleftsubtreeuptodeletenode
    107. sub_root=sub_root->left;
    108. if(sub_root->get_balance()==left_higher){
    109. //Neithersubtreeisempty;deletefromthetaller
    110. temp=sub_root->left;//Findpredecessoroftargetanddeleteiffromlefttree
    111. while(temp->right!=NULL)temp=temp->right;
    112. sub_root->data=temp->data;
    113. avl_remove_left(sub_root,temp->data,shorter);
    114. temp=sub_root->right;
    115. while(temp->left!=NULL)temp=temp->left;
    116. avl_remove_right(sub_root,153); background-color:inherit; font-weight:bold">returnsuccess;
    117. Error_codeAVL_tree<Record>::avl_remove_right(Binary_node<Record>
    118. *&sub_root,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> Error_coderesult=avl_remove(sub_root->right,shorter);
    119. if(shorter==true)switch(sub_root->get_balance()){
    120. sub_root->set_balance(equal_height);
    121. Binary_node<Record>*temp=sub_root->left;
    122. switch(temp->get_balance()){
    123. temp->set_balance(right_higher);
    124. shorter= temp->set_balance(equal_height);
    125. Binary_node<Record>*temp_right=temp->right;
    126. switch(temp_right->get_balance()){
    127. temp->set_balance(left_higher);
    128. temp_right->set_balance(equal_height);
    129. rotate_left(sub_root->left);
    130. Error_codeAVL_tree<Record>::avl_remove_left(Binary_node<Record>
    131. *&sub_root,87); background-color:inherit; font-weight:bold">bool&shorter)
    132. Error_coderesult=avl_remove(sub_root->left,248); line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> sub_root->set_balance(right_higher);
    133. Binary_node<Record>*temp=sub_root->right;
    134. Binary_node<Record>*temp_left=temp->left;
    135. switch(temp_left->get_balance()){
    136. sub_root->set_balance(left_higher);
    137. temp_left->set_balance(equal_height);
    138. rotate_right(sub_root->right);
    139. }


    实验结果

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

    分析总结

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

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

    实现AVL树的相关运算

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

    转载请注明出处：http://www.52php.cn/article/p-mgfuopiu-vo.html

    （编辑：李大同）

    【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
    相关内容
      推荐文章
        站长推荐
        热点阅读

          【免责声明】本站内容转载自互联网，其发布内容言论不代表本站观点，如果其链接、内容的侵犯您的权益，烦请提交相关链接至邮箱bqsm@foxmail.com我们将及时予以处理。

          建议您使用1920×1080分辨率、谷歌浏览器Google Chrome、Microsoft Edge以获得本站的最佳浏览效果

          Copygight © 2008-2022 https://www.lidatong.com.cn/ All Rights Reserved. 李大同