圆月山庄资源网

python 平衡二叉树实现代码示例
脚本专栏 2024/11/7 佚名
3 2
圆月山庄资源网 Design By www.vgjia.com

平衡二叉树：

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

所谓平衡二叉树：

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

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

　　python 平衡二叉树实现代码示例

此时的处理办法就是：

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

此时分两种情况：

一、左枝有最右节点

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

二、左枝没有最右节点，

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

　　　　　　python 平衡二叉树实现代码示例

如图所示，图更清楚些。

可能会有疑问，为什么这样变换？

假定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 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)

执行结果：

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

通过前序可以画出二叉树

python 平衡二叉树实现代码示例

完美，哈哈。

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

下一步就是代码优化了

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

标签：
python,平衡二叉树,平衡二叉树,python
圆月山庄资源网 Design By www.vgjia.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
圆月山庄资源网 Design By www.vgjia.com
www.vgjia.com 圆月山庄资源网
139,976互联网资源
144,792高清电影
21,817无损音乐
631,128技术资源

P70系列延期，华为新旗舰将在下月发布

3月20日消息，近期博主@数码闲聊站 透露，原定三月份发布的华为新旗舰P70系列延期发布，预计4月份上市。

而博主@定焦数码 爆料，华为的P70系列在定位上已经超过了Mate60，成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢？

根据目前爆料的消息来看，华为P70系列将推出三个版本，其中P70和P70 Pro采用了三角形的摄像头模组设计，而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智，但辨识度绝对拉满。

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接