平衡二叉樹：

在上一節二叉樹的基礎上我們實現，如何將生成平衡的二叉樹

所謂平衡二叉樹：

我自己定義就是：任何一個節點的左高度和右高度的差的絕對值都小于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了

處理了所有節點 的左偏和右偏使整個二叉樹平衡，這就是平衡二叉樹的基本思想

代碼實現：

# -*- coding:utf-8 -*-# 日期：2018/6/12 8:37# Author:小鼠標# 節點對象class Node:  def __init__(self):    self.left_children = None    self.left_height = 0    self.right_children = None    self.right_height = 0    self.value = None# 二叉樹對象class tree:  def __init__(self):    self.root = False    self.front_list = []    self.middle_list = []    self.after_list = []  # 生成二叉樹  def create_tree(self,n=0,l=[]):    if l == []:      print("傳入的列表為空")      return    if n > len(l)-1:      print("二叉樹生成")      return    node = Node()    node.value = l[n]    if not self.root:      self.root = node      self.list = l    else:      self.add(self.root,node)    self.create_tree(n+1,l)  # 添加節點  def add(self,parent,new_node):    if new_node.value > parent.value:      # 插入值比父親值大，所以在父節點右邊      if parent.right_children == None:        parent.right_children = new_node        # 新插入節點的父親節點的高度值為1，也就是子高度值0+1        parent.right_height = 1        # 插入值后 從下到上更新節點的height      else:        self.add(parent.right_children,new_node)        # 父親節點的右高度等于右孩子，左右高度中較大的值 + 1        parent.right_height = max(parent.right_children.right_height, parent.right_children.left_height) + 1        # ======= 此處開始判斷平衡二叉樹=======        # 右邊高度大于左邊高度 屬于右偏        if parent.right_height - parent.left_height >= 2:          self.right_avertence(parent)    else:      # 插入值比父親值小，所以在父節點左邊      if parent.left_children == None:        parent.left_children = new_node        parent.left_height = 1      else:        self.add(parent.left_children,new_node)        parent.left_height = max(parent.left_children.right_height, parent.left_children.left_height) + 1        # ======= 此處開始判斷平衡二叉樹=======        # 左邊高度大于右邊高度 屬于左偏        if parent.left_height - parent.right_height >= 2:          self.left_avertence(parent)  # 更新當前節點下的所有節點的高度  def update_height(self,node):    # 初始化節點高度值為0    node.left_height = 0    node.right_height = 0    # 是否到最底層的一個    if node.left_children == None and node.right_children == None:      return    else:      if node.left_children:        self.update_height(node.left_children)        # 當前節點的高度等于左右子節點高度的較大值 + 1        node.left_height = max(node.left_children.left_height,node.left_children.right_height) + 1      if node.right_children:        self.update_height(node.right_children)        # 當前節點的高度等于左右子節點高度的較大值 + 1        node.right_height = max(node.right_children.left_height, node.right_children.right_height) + 1      # 檢查是否仍有不平衡      if node.left_height - node.right_height >= 2:        self.left_avertence(node)      elif node.left_height - node.right_height <= -2:        self.right_avertence(node)  def right_avertence(self,node):    # 右偏 就將當前節點的最左節點做父親    new_code = Node()    new_code.value = node.value    new_code.left_children = node.left_children    best_left = self.best_left_right(node.right_children)    v = node.value    # 返回的對象本身,    if best_left == node.right_children and best_left.left_children == None:      # 說明當前節點沒有有節點      node.value = best_left.value      node.right_children = best_left.right_children    else:      node.value = best_left.left_children.value      best_left.left_children = best_left.left_children.right_children    node.left_children = new_code    self.update_height(node)  # 處理左偏情況  def left_avertence(self,node):    new_code = Node()    new_code.value = node.value    new_code.right_children = node.right_children    best_right = self.best_left_right(node.left_children,1)    v = node.value    # 返回的對象本身,    if best_right == node.left_children and best_right.right_children == None:      # 說明當前節點沒有有節點      node.value = best_right.value      node.left_children = best_right.left_children    else:      node.value = best_right.right_children.value      best_right.right_children = best_right.right_children.left_children    node.right_children = new_code    self.update_height(node)  # 返回node節點最左（右）子孫的父級  def best_left_right(self,node,type=0):    # type=0 默認找最左子孫    if type == 0:      if node.left_children == None:        return node      elif node.left_children.left_children == None:        return node      else:        return self.best_left_right(node.left_children,type)    else:      if node.right_children == None:        return node      elif node.right_children.right_children == None:        return node      else:        return self.best_left_right(node.right_children,type)  # 前序(先中再左最后右)  def front(self,node=None):    if node == None:      self.front_list = []      node = self.root    # 輸出當前節點    self.front_list.append(node.value)    # 先判斷左枝    if not node.left_children == None:      self.front(node.left_children)    # 再判斷右枝    if not node.right_children == None:      self.front(node.right_children)    # 返回最終結果    return self.front_list  # 中序(先左再中最后右)  def middle(self,node=None):    if node == None:      node = self.root    # 先判斷左枝    if not node.left_children == None:      self.middle(node.left_children)    # 輸出當前節點    self.middle_list.append(node.value)    # 再判斷右枝    if not node.right_children == None:      self.middle(node.right_children)    return self.middle_list  # 后序(先左再右最后中)  def after(self,node=None):    if node == None:      node = self.root    # 先判斷左枝    if not node.left_children == None:      self.after(node.left_children)    # 再判斷右枝    if not node.right_children == None:      self.after(node.right_children)    self.after_list.append(node.value)    return self.after_list  # 節點刪除  def del_node(self,v,node=None):    if node == None:      node = self.root      # 刪除根節點      if node.value == v:        self.del_root(self.root)        return    # 刪除當前節點的左節點    if node.left_children:      if node.left_children.value == v:        self.del_left(node)        return    # 刪除當前節點的右節點    if node.right_children:      if node.right_children.value == v:        self.del_right(node)        return    if v > node.value:      if node.right_children:        self.del_node(v, node.right_children)      else:        print("刪除的元素不存在")    else:      if node.left_children:        self.del_node(v, node.left_children)      else:        print("刪除的元素不存在")  #刪除當前節點的右節點  def del_right(self,node):    # 情況1 刪除節點沒有右枝    if node.right_children.right_children == None:      node.right_children = node.right_children.left_children    else:      best_left = self.best_left_right(node.right_children.right_children)      # 表示右枝最左孫就是右枝本身      if best_left == node.right_children.right_children and best_left.left_children == None:        node.right_children.value = best_left.value        node.right_children.right_children = best_left.right_children      else:        node.right_children.value = best_left.left_children.value        best_left.left_children = best_left.left_children.right_children  # 刪除當前節點的左節點  def del_left(self,node):    # 情況1 刪除節點沒有右枝    if node.left_children.right_children == None:      node.left_children = node.left_children.left_children    else:      best_left = self.best_left_right(node.left_children.right_children)      # 表示右枝最左子孫就是右枝本身      if best_left == node.left_children.right_children and best_left.left_children == None:        node.left_children.value = best_left.value        node.left_children.right_children = best_left.right_children      else:        node.left_children.value = best_left.left_children.value        best_left.left_children = best_left.left_children.right_children  # 刪除根節點  def del_root(self,node):    if node.right_children == None:      if node.left_children == None:        node.value = None      else:        self.root = node.left_children    else:      best_left = self.best_left_right(node.right_children)      # 表示右枝最左子孫就是右枝本身      if best_left == node.right_children and best_left.left_children == None:        node.value = best_left.value        node.right_children = best_left.right_children      else:        node.value = best_left.left_children.value        best_left.left_children = best_left.left_children.right_children  # 搜索  def search(self,v,node=None):    if node == None:      node = self.root    if node.value == v:      return True    if v > node.value:      if not node.right_children == None:        return self.search(v, node.right_children)    else:      if not node.left_children == None:        return self.search(v, node.left_children)    return Falseif __name__ == '__main__':  # 需要建立二叉樹的列表  list = [4, 6, 3, 1, 7, 9, 8, 5, 2]  t = tree()  t.create_tree(0,list)  res = t.front()  print('前序', res)