Python实现平衡二叉树：旋转原理与代码详解
发布时间：2026-10-13 |
2人浏览过
本文详细解析平衡二叉树的定义与不平衡处理机制，重点阐述左偏与右偏时的旋转策略。通过具体节点示例说明为何选择特定子节点作为新根，并附带完整的Python代码实现及前序遍历结果验证，帮助开发者理解平衡二叉树的构建逻辑。
平衡二叉树：
基于前文介绍的二叉树结构，本节将深入探讨如何构建和维护一棵平衡二叉树。
关于平衡二叉树的定义：
个人理解，平衡二叉树的核心标准是：任意节点的左子树高度与右子树高度之差的绝对值必须严格小于2。
参考图示，节点a的左子树高度为3，右子树高度为1，两者差值为2，这属于不平衡状态中的左偏情形。
针对上述不平衡情况，处理方法如下：
将导致不平衡节点的左子树中最右侧的节点提升为当前子树的根节点。
此过程需分两种具体场景讨论：
第一种情况：左子树存在最右侧节点。
将该最右侧节点的左子树挂载到其原父节点的右子树位置。
第二种情况：左子树不存在最右侧节点。
直接将该左子树节点提升为父级节点，原父节点则变为新节点的右子树。
如图所示，图示能更直观地展示这一过程。
读者可能会疑惑，为何要采用这种变换方式？
假设节点a发生左偏，我们需要找到一个比a小且大于a左子树所有节点的值d作为新的父节点，并将a设为d的右子树，从而在顶层实现平衡。
我们可以通过反证法来验证：
假设选择另一个值h作为父节点，而a作为其右子节点。
由于a位于h的右侧，根据二叉搜索树性质，必有 a > h。
同时，b、e、d、f均位于h的左子树中，因此 h > d > b > e > f。
综合上述关系，可得 a > h > d > b > e > f。
因此，在不引入新节点的前提下，只有d具备成为平衡父节点的资格。
右偏情况的处理逻辑与左偏完全镜像对称，只需执行对应的反向旋转操作即可。
通过对所有节点的左偏和右偏情况进行处理，使整棵二叉树达到平衡状态，这便是平衡二叉树的核心思想。
代码实现部分：
# -*- 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]
根据前序遍历序列可以重构出对应的二叉树结构。
结果完美，令人欣慰。
这段代码经过两天的钻研才完成，虽然辛苦但收获颇丰，继续加油。
接下来的工作重点是代码优化。
以上就是本文的全部内容，希望能为各位的学习提供参考，也欢迎大家继续支持本站。
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
