|
目录
平衡二叉树的主要操作
AVL.py
tree.py
github:
平衡二叉树的主要操作
"""FUN0 初始化"""
"""FUN1 由无序数组创建平衡二叉树 """
"""FUN2 向平衡二叉树添加节点 """
"""FUN3 将二叉树恢复平衡"""
"""FUN4 计算每个结点的height"""
"""FUN5 计算每个结点的balance"""
"""FUN6 左旋"""
"""FUN7 右旋"""
"""FUN9 中序遍历平衡二叉树，并打印结果"""
"""FUN10 打印平衡二叉树图形"""
"""FUN11 将平衡二叉树转化为普通的二叉树"""
AVL.py
"""
平衡二叉树
"""
from tree import *
class AvlTree(object):
"""FUN0 初始化"""
def __init__(self):
self.node = None
self.height = -1
self.balance = 0
"""FUN1 由无序数组创建平衡二叉树 """
def avl_create(self, arr):
for i in arr:
self.avl_insert(i)
"""FUN2 向平衡二叉树添加节点 """
def avl_insert(self, val):
node = TreeNode(val)
if self.node is None:
self.node = node
self.node.left = AvlTree()
self.node.right = AvlTree()
elif val < self.node.val:
self.node.left.avl_insert(val)
else:
self.node.right.avl_insert(val)
# 调整使平衡
self.avl_rebalance()
"""FUN3 将二叉树恢复平衡"""
def avl_rebalance(self):
# 计算平衡因子
self.avl_heights(False)
self.avl_balance(False)
while self.balance < -1 or self.balance > 1:
if self.balance < -1: # R
if self.node.right.balance > 0: # 如果是RL
self.node.right.avl_rotate_right() # 对RL需要先转化成RR
self.avl_heights()
self.avl_balance()
self.avl_rotate_left() # RR
self.avl_heights()
self.avl_balance()
if self.balance > 1: # L
if self.node.left.balance < 0: # 如果是LR
self.node.left.avl_rotate_left() # 对LR需要先转换成LL
self.avl_heights()
self.avl_balance()
self.avl_rotate_right() # LL
self.avl_heights()
self.avl_balance()
"""FUN4 计算每个结点的height"""
def avl_heights(self, recursive=True):
if self.node is None:
self.height = -1
else:
if recursive: # 在插入结点时计算高度，由上到下计算高度； 结点调换位置时，由下到上计算高度
if self.node.left:
self.node.left.avl_heights()
if self.node.right:
self.node.right.avl_heights()
self.height = 1 + max(self.node.left.height, self.node.right.height)
"""FUN5 计算每个结点的balance"""
def avl_balance(self, recursive=True):
if self.node is None:
self.balance = 0
else:
if recursive:
if self.node.left:
self.node.left.avl_balance()
if self.node.right:
self.node.right.avl_balance()
self.balance = self.node.left.height - self.node.right.height
"""FUN6 左旋"""
def avl_rotate_left(self):
new_root = self.node.right.node
new_sub_left = new_root.left.node
old_root = self.node
self.node = new_root
old_root.right.node = new_sub_left
new_root.left.node = old_root
"""FUN7 右旋"""
def avl_rotate_right(self):
new_root = self.node.left.node
new_sub_right = new_root.right.node
old_root = self.node
self.node = new_root
old_root.left.node = new_sub_right
new_root.right.node = old_root
"""FUN9 中序遍历平衡二叉树"""
def avl_inorder(self):
if self.node is None:
return
if self.node.left:
self.node.left.avl_inorder()
print("val:{}, height:{}, balance:{}".format(self.node.val, self.height, self.balance))
if self.node.right:
self.node.right.avl_inorder()
"""FUN10 打印平衡二叉树图形"""
def avl_print_graph(self):
"""FUN11 将平衡二叉树转化为普通的二叉树"""
root = self.acl2Btree()
# 打印转化后的树
tree_print_graph(root)
"""FUN11 将平衡二叉树转化为普通的二叉树"""
def acl2Btree(self):
if self.node is None:
return
root = TreeNode(self.node.val)
if self.node.left:
root.left = self.node.left.acl2Btree()
if self.node.right:
root.right = self.node.right.acl2Btree()
return root
arr = [1, 2, 3, 4, 5, 6]
# arr = [3, 4, 2, 1, 6, 5]
# arr = [-10, -3, 0, 5, 9]
"""FUN0 初始化"""
avl = AvlTree()
"""FUN1 由无序数组创建平衡二叉树 """
avl.avl_create(arr)
"""FUN9 中序遍历平衡二叉树"""
avl.avl_inorder()
"""FUN10 打印平衡二叉树图形"""
avl.avl_print_graph()
tree.py
from typing import List
from pyasn1.compat.octets import null
"""二叉树数据结构"""
class TreeNode:
def __init__(self, val=-1):
self.val = val
self.left = None
self.right = None
"""FUN2.3 层次遍历一棵树，以数组的形式返回遍历结果(与原树高度相同的完全二叉树，空结点-1补全), 用于绘制图形"""
def tree_level_complete_binary_tree(root):
if root is None:
return
depth = tree_depth(root)
tree_graph = []
queue = [root]
while queue:
node = queue.pop(0)
tree_graph.append(node.val)
if node.left:
queue.append(node.left)
else:
queue.append(TreeNode())
if node.right:
queue.append(node.right)
else:
queue.append(TreeNode())
tag = True # 全是null
for q in queue:
if q.val != -1:
tag = False
if tag: # 全是null
break
for i in range(len(tree_graph), 2 ** depth - 1):
tree_graph.append(-1)
return tree_graph
"""FUN3 求一棵树的最大深度"""
def tree_depth(root) -> int:
return 0 if root is None else max(tree_depth(root.left), tree_depth(root.right)) + 1
"""FUN4 打印一棵二叉树图形"""
def tree_print_graph(root):
depth = tree_depth(root)
tree_graph = tree_level_complete_binary_tree(root)
# print(tree_graph)
nodes_val = [[] for i in range(depth)] # 记录每一层的结点
graph = ["" for i in range(depth)]
# 排列好结点的位置
for i in range(depth):
nodes_val[i] = tree_graph[2 ** i - 1: 2 ** (i + 1) - 1]
# print(nodes_val)
for j in range(len(nodes_val[i])):
if nodes_val[i][j] == -1:
nodes_val[i][j] = " "
graph[i] += str(nodes_val[i][j]) + (" " * (2 ** (depth - i + 1) - 1)) # 添加结点之间的间隔,最底层间隔3个“ ”
# print(graph[i])
graph[i] = (" " * ((2 ** (depth - i)) - 2)) + graph[i] # 错开位置,构成树的形状，
# print(graph[i])
# print("###################################################################")
for s in graph:
print(s)
github:
https://github.com/YTIANYE/PractisePython/tree/master/%E5%88%9D%E7%BA%A7%E7%AE%97%E6%B3%95-%E5%B8%AE%E5%8A%A9%E5%85%A5%E9%97%A8/05%E6%A0%91
|