python 平衡二叉樹實現(xiàn)代碼示例

更新時間：2018年07月07日 11:54:20 作者：7749ha

這篇文章主要介紹了python 平衡二叉樹實現(xiàn)代碼示例，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

平衡二叉樹：

在上一節(jié)二叉樹的基礎(chǔ)上我們實現(xiàn)，如何將生成平衡的二叉樹

所謂平衡二叉樹：

我自己定義就是：任何一個節(jié)點的左高度和右高度的差的絕對值都小于2

如圖所示，此時a的左高度等于3，有高度等于1，差值為2，屬于不平衡中的左偏

此時的處理辦法就是：

將不平衡的元素的左枝的最右節(jié)點變?yōu)楫?dāng)前節(jié)點，

此時分兩種情況：

一、左枝有最右節(jié)點

將最右節(jié)點的左枝賦予其父節(jié)點的右枝

二、左枝沒有最右節(jié)點，

直接將左枝節(jié)點做父級節(jié)點，父級節(jié)點做其右枝

如圖所示，圖更清楚些。

可能會有疑問，為什么這樣變換？

假定a左偏，就需要一個比a小的最少一個值d(因為d唯一一個是比a小，而且比a的左枝所有數(shù)都大的值)做父集結(jié)點，a做d的右枝，這樣在最上面的d節(jié)點就平衡了。

我們可以反證一下：

如果不是d是另一個數(shù)假設(shè)為h，此時h做父節(jié)點，a做父節(jié)點的右節(jié)點

因為a在h右邊，所以 a > h

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

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

所以在不加入新節(jié)點的情況下，就只能是d　　　　

左偏和右偏是一樣的，可以完全鏡像過來就ok了

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

代碼實現(xiàn)：

# -*- coding:utf-8 -*-
# 日期：2018/6/12 8:37
# Author:小鼠標(biāo)

# 節(jié)點對象
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)
  # 添加節(jié)點
  def add(self,parent,new_node):
    if new_node.value > parent.value:
      # 插入值比父親值大，所以在父節(jié)點右邊
      if parent.right_children == None:
        parent.right_children = new_node
        # 新插入節(jié)點的父親節(jié)點的高度值為1，也就是子高度值0+1
        parent.right_height = 1
        # 插入值后 從下到上更新節(jié)點的height
      else:
        self.add(parent.right_children,new_node)
        # 父親節(jié)點的右高度等于右孩子，左右高度中較大的值 + 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:
      # 插入值比父親值小，所以在父節(jié)點左邊
      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)
  # 更新當(dāng)前節(jié)點下的所有節(jié)點的高度
  def update_height(self,node):
    # 初始化節(jié)點高度值為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)
        # 當(dāng)前節(jié)點的高度等于左右子節(jié)點高度的較大值 + 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)
        # 當(dāng)前節(jié)點的高度等于左右子節(jié)點高度的較大值 + 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):
    # 右偏 就將當(dāng)前節(jié)點的最左節(jié)點做父親
    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:
      # 說明當(dāng)前節(jié)點沒有有節(jié)點
      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:
      # 說明當(dāng)前節(jié)點沒有有節(jié)點
      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節(jié)點最左（右）子孫的父級
  def best_left_right(self,node,type=0):
    # type=0 默認(rèn)找最左子孫
    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
    # 輸出當(dāng)前節(jié)點
    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)
    # 返回最終結(jié)果
    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)
    # 輸出當(dāng)前節(jié)點
    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
  # 節(jié)點刪除
  def del_node(self,v,node=None):
    if node == None:
      node = self.root
      # 刪除根節(jié)點
      if node.value == v:
        self.del_root(self.root)
        return
    # 刪除當(dāng)前節(jié)點的左節(jié)點
    if node.left_children:
      if node.left_children.value == v:
        self.del_left(node)
        return
    # 刪除當(dāng)前節(jié)點的右節(jié)點
    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("刪除的元素不存在")
  #刪除當(dāng)前節(jié)點的右節(jié)點
  def del_right(self,node):
    # 情況1 刪除節(jié)點沒有右枝
    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
  # 刪除當(dāng)前節(jié)點的左節(jié)點
  def del_left(self,node):
    # 情況1 刪除節(jié)點沒有右枝
    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
  # 刪除根節(jié)點
  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 False
if __name__ == '__main__':
  # 需要建立二叉樹的列表
  list = [4, 6, 3, 1, 7, 9, 8, 5, 2]
  t = tree()
  t.create_tree(0,list)
  res = t.front()
  print('前序', res)

執(zhí)行結(jié)果：

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

通過前序可以畫出二叉樹