在上一节二叉树的基础上我们实现，如何将生成平衡的二叉树

　　所谓平衡二叉树：

　　　　我自己定义就是：任何一个节点的左高度和右高度的差的绝对值都小于2

　　　　如图所示，此时a的左高度等于3，有高度等于1，差值为2，属于不平衡中的左偏

　　

　　此时的处理办法就是：

　　　　将不平衡的元素的左枝的最右节点变为当前节点，

　　　　此时分两种情况：

　　　　　一、左枝有最右节点

　　　　　　将最右节点的左枝赋予其父节点的右枝

　　　　　二、左枝没有最右节点，

　　　　　　直接将左枝节点做父级节点，父级节点做其右枝

　　　　　　

 

　　如图所示，图更清楚些。

　　　　假定a左偏，就需要一个比a小的最少一个值d(因为d唯一 一个是比a小，而且比a的左枝所有数都大的值)做父集结点，a做d的右枝，这样在最上面的d节点就平衡了。

　　　　我们可以反证一下：

　　　　　如果不是d是另一个数假设为h，此时h做父节点，a做父节点的右节点

　　　　  因为a在h右边，所以 a > h

　　　　  因为b,e,d,f都是h的左枝，所以  h>d>b>e>f

　　　　  所以 a>h>d>b>e>f

　　　　  所以在不加入新节点的情况下，就只能是d　　　　

 

左偏和右偏是一样的，可以完全镜像过来就ok了

处理了所有节点 的左偏和右偏使整个二叉树平衡，这就是平衡二叉树的基本思想

  1. # -*- coding:utf-8  -*-
  2. # 日期：2018/6/12 8:37
  3. # Author:小鼠标
  4.  
  5. # 节点对象
  6. class Node:
  7.     def __init__(self):
  8.         self.left_children = None
  9.         self.left_height = 0
  10.         self.right_children = None
  11.         self.right_height = 0
  12.         self.value = None
  14. # 二叉树对象
  15. class tree:
  16.     def __init__(self):
  17.         self.root = False
  18.         self.front_list = []
  19.         self.middle_list = []
  20.         self.after_list = []
  21.     # 生成二叉树
  22.     def create_tree(self,n=0,l=[]):
  23.         if l == []:
  24.             print("传入的列表为空")
  25.             return
  26.         if n > len(l)-1:
  27.             print("二叉树生成")
  28.             return
  29.         node = Node()
  30.         node.value = l[n]
  31.         if not self.root:
  32.            self.root = node
  33.            self.list = l
  34.         else:
  35.             self.add(self.root,node)
  36.         self.create_tree(n+1,l)
  37.     # 添加节点
  38.     def add(self,parent,new_node):
  39.         if new_node.value > parent.value:
  40.             # 插入值比父亲值大，所以在父节点右边
  41.             if parent.right_children == None:
  42.                 parent.right_children = new_node
  43.                 # 新插入节点的父亲节点的高度值为1，也就是子高度值0+1
  44.                 parent.right_height = 1
  45.                 # 插入值后 从下到上更新节点的height
  46.             else:
  47.                 self.add(parent.right_children,new_node)
  48.                 # 父亲节点的右高度等于右孩子，左右高度中较大的值 + 1
  49.                 parent.right_height = max(parent.right_children.right_height, parent.right_children.left_height) + 1
  50.                 # ======= 此处开始判断平衡二叉树=======
  51.                 # 右边高度大于左边高度 属于右偏
  52.                 if parent.right_height - parent.left_height >= 2:
  53.                     self.right_avertence(parent)
  54.         else:
  55.             # 插入值比父亲值小，所以在父节点左边
  56.             if parent.left_children == None:
  57.                 parent.left_children = new_node
  58.                 parent.left_height = 1
  59.             else:
  60.                 self.add(parent.left_children,new_node)
  61.                 parent.left_height = max(parent.left_children.right_height, parent.left_children.left_height) + 1
  62.                 # ======= 此处开始判断平衡二叉树=======
  63.                 # 左边高度大于右边高度 属于左偏
  64.                 if parent.left_height - parent.right_height >= 2:
  65.                     self.left_avertence(parent)
  66.     # 更新当前节点下的所有节点的高度
  67.     def update_height(self,node):
  68.         # 初始化节点高度值为0
  69.         node.left_height = 0
  70.         node.right_height = 0
  71.         # 是否到最底层的一个
  72.         if node.left_children == None and node.right_children == None:
  73.             return
  74.         else:
  75.             if node.left_children:
  76.                 self.update_height(node.left_children)
  77.                 # 当前节点的高度等于左右子节点高度的较大值 + 1
  78.                 node.left_height = max(node.left_children.left_height,node.left_children.right_height) + 1
  79.             if node.right_children:
  80.                 self.update_height(node.right_children)
  81.                 # 当前节点的高度等于左右子节点高度的较大值 + 1
  82.                 node.right_height = max(node.right_children.left_height, node.right_children.right_height) + 1
  83.             # 检查是否仍有不平衡
  84.             if node.left_height - node.right_height >= 2:
  85.                 self.left_avertence(node)
  86.             elif node.left_height - node.right_height <= -2:
  87.                 self.right_avertence(node)
  89.     def right_avertence(self,node):
  90.         # 右偏 就将当前节点的最左节点做父亲
  91.         new_code = Node()
  92.         new_code.value = node.value
  93.         new_code.left_children = node.left_children
  94.         best_left = self.best_left_right(node.right_children)
  95.         v = node.value
  96.         # 返回的对象本身,
  97.         if best_left == node.right_children and best_left.left_children == None:
  98.             # 说明当前节点没有有节点
  99.             node.value = best_left.value
  100.             node.right_children = best_left.right_children
  101.         else:
  102.             node.value = best_left.left_children.value
  103.             best_left.left_children = best_left.left_children.right_children
  104.         node.left_children = new_code
  105.         self.update_height(node)
  107.     # 处理左偏情况
  108.     def left_avertence(self,node):
  109.         new_code = Node()
  110.         new_code.value = node.value
  111.         new_code.right_children = node.right_children
  112.         best_right = self.best_left_right(node.left_children,1)
  113.         v = node.value
  114.         # 返回的对象本身,
  115.         if best_right == node.left_children and best_right.right_children == None:
  116.             # 说明当前节点没有有节点
  117.             node.value = best_right.value
  118.             node.left_children = best_right.left_children
  119.         else:
  120.             node.value = best_right.right_children.value
  121.             best_right.right_children = best_right.right_children.left_children
  122.         node.right_children = new_code
  123.         self.update_height(node)
  124.     # 返回node节点最左（右）子孙的父级
  125.     def best_left_right(self,node,type=0):
  126.         # type=0 默认找最左子孙
  127.         if type == 0:
  128.             if node.left_children == None:
  129.                 return node
  130.             elif node.left_children.left_children == None:
  131.                 return node
  132.             else:
  133.                 return self.best_left_right(node.left_children,type)
  134.         else:
  135.             if node.right_children == None:
  136.                 return node
  137.             elif node.right_children.right_children == None:
  138.                 return node
  139.             else:
  140.                 return self.best_left_right(node.right_children,type)
  141.     # 前序(先中再左最后右)
  142.     def front(self,node=None):
  143.         if node == None:
  144.             self.front_list = []
  145.             node = self.root
  146.         # 输出当前节点
  147.         self.front_list.append(node.value)
  148.         # 先判断左枝
  149.         if not node.left_children == None:
  150.             self.front(node.left_children)
  151.         # 再判断右枝
  152.         if not node.right_children == None:
  153.             self.front(node.right_children)
  154.         # 返回最终结果
  155.         return self.front_list
  156.     # 中序(先左再中最后右)
  157.     def middle(self,node=None):
  158.         if node == None:
  159.             node = self.root
  160.         # 先判断左枝
  161.         if not node.left_children == None:
  162.             self.middle(node.left_children)
  163.         # 输出当前节点
  164.         self.middle_list.append(node.value)
  165.         # 再判断右枝
  166.         if not node.right_children == None:
  167.             self.middle(node.right_children)
  168.         return self.middle_list
  169.     # 后序(先左再右最后中)
  170.     def after(self,node=None):
  171.         if node == None:
  172.             node = self.root
  173.         # 先判断左枝
  174.         if not node.left_children == None:
  175.             self.after(node.left_children)
  176.         # 再判断右枝
  177.         if not node.right_children == None:
  178.             self.after(node.right_children)
  179.         self.after_list.append(node.value)
  180.         return self.after_list
  181.     # 节点删除
  182.     def del_node(self,v,node=None):
  183.         if node == None:
  184.             node = self.root
  185.             # 删除根节点
  186.             if node.value == v:
  187.                 self.del_root(self.root)
  188.                 return
  189.         # 删除当前节点的左节点
  190.         if node.left_children:
  191.             if node.left_children.value == v:
  192.                 self.del_left(node)
  193.                 return
  194.         # 删除当前节点的右节点
  195.         if node.right_children:
  196.             if node.right_children.value == v:
  197.                 self.del_right(node)
  198.                 return
  199.         if v > node.value:
  200.             if node.right_children:
  201.                 self.del_node(v, node.right_children)
  202.             else:
  203.                 print("删除的元素不存在")
  204.         else:
  205.             if node.left_children:
  206.                 self.del_node(v, node.left_children)
  207.             else:
  208.                 print("删除的元素不存在")
  209.     #删除当前节点的右节点
  210.     def del_right(self,node):
  211.         # 情况1 删除节点没有右枝
  212.         if node.right_children.right_children == None:
  213.             node.right_children = node.right_children.left_children
  214.         else:
  215.             best_left = self.best_left_right(node.right_children.right_children)
  216.             # 表示右枝最左孙就是右枝本身
  217.             if best_left == node.right_children.right_children and best_left.left_children == None:
  218.                 node.right_children.value = best_left.value
  219.                 node.right_children.right_children = best_left.right_children
  220.             else:
  221.                 node.right_children.value = best_left.left_children.value
  222.                 best_left.left_children = best_left.left_children.right_children
  223.     # 删除当前节点的左节点
  224.     def del_left(self,node):
  225.         # 情况1 删除节点没有右枝
  226.         if node.left_children.right_children == None:
  227.             node.left_children = node.left_children.left_children
  228.         else:
  229.             best_left = self.best_left_right(node.left_children.right_children)
  230.             # 表示右枝最左子孙就是右枝本身
  231.             if best_left == node.left_children.right_children and best_left.left_children == None:
  232.                 node.left_children.value = best_left.value
  233.                 node.left_children.right_children = best_left.right_children
  234.             else:
  235.                 node.left_children.value = best_left.left_children.value
  236.                 best_left.left_children = best_left.left_children.right_children
  237.     # 删除根节点
  238.     def del_root(self,node):
  239.         if node.right_children == None:
  240.             if node.left_children == None:
  241.                 node.value = None
  242.             else:
  243.                 self.root = node.left_children
  244.         else:
  245.             best_left = self.best_left_right(node.right_children)
  246.             # 表示右枝最左子孙就是右枝本身
  247.             if best_left == node.right_children and best_left.left_children == None:
  248.                 node.value = best_left.value
  249.                 node.right_children = best_left.right_children
  250.             else:
  251.                 node.value = best_left.left_children.value
  252.                 best_left.left_children = best_left.left_children.right_children
  254.     # 搜索
  255.     def search(self,v,node=None):
  256.         if node == None:
  257.             node = self.root
  258.         if node.value == v:
  259.             return True
  260.         if v > node.value:
  261.             if not node.right_children == None:
  262.                 return self.search(v, node.right_children)
  263.         else:
  264.             if not node.left_children == None:
  265.                 return self.search(v, node.left_children)
  266.         return False
  267. if __name__ == \'__main__\':
  268.     # 需要建立二叉树的列表
  269.     list = [4, 6, 3, 1, 7, 9, 8, 5, 2]
  270.     t = tree()
  271.     t.create_tree(0,list)
  272.     res = t.front()
  273.     print(\'前序\', res)

执行结果：

　　前序 [4, 2, 1, 3, 7, 6, 5, 9, 8]

　　通过前序可以画出二叉树

完美，哈哈。

这是我钻了两天才写出的代码，哈哈，努力还是有回报的，加油。

 下一步就是代码优化了

版权声明：本文为7749ha原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/7749ha/p/9179086.html