【AVL树】python实现动态可视化
本帖最后由 Lthero 于 2022-11-16 22:11 编辑最近复习数据结构，翻出快一年前写的代码……感慨当时好nb。
源码语言：
python
可视化：
tkinter实现
功能：
动态添加数据并构建可视化AVL树
删除部分有bug，懒得修了……
PS:
此代码为课程作业，部分地方写得不好，请大家不要喷……
本代码效果：
添加1~5【可以乱序添加】
添加6、7
添加8、9、10等数【距离会随着数据变多而改变】
AVL基础内容查看：https://www.52pojie.cn/thread-1422907-1-1.html
AVL可视化体验【来源于互联网】：https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
代码
from tkinter import Tk, ttk, font
from tkinter import *
Width = 1200
Height = 700
col_0 = 120
row_0 = 40
row_1 = 70
class node():
def __init__(self, value=0, left=None, right=None, pre=None):
self.value = value
self.left = left
self.right = right
self.r_height = 0
self.l_height = 0
self.pre = pre
class link():
def __init__(self, value):
self.head = node(value)
self.length = 0
def T_adj(self, the_node):
p = the_node
if p is not None:
x = p.value
if abs(p.l_height - p.r_height) >= 2:
self.adj(p)
return self.T_adj(p.pre)
return
def adj(self, the_node):
p = the_node
if p.l_height - p.r_height >= 2:
if p.left.right is None:
# print('直接右转 ', p.value)
self.r_rotate(p)
else:
if p.left.left is not None:
self.r_rotate(p)
else:
# print('先左转%d再右转%d' % (p.left.value, p.value))
self.l_rotate(p.left)
self.r_rotate(p)
if p.r_height - p.l_height >= 2:
if p.right.left is None:
# print('直接左转', p.value)
self.l_rotate(p)
else:
if p.right.right is not None:
self.l_rotate(p)
else:
# print('先右转%d再左转%d' % (p.right.value, p.value))
self.r_rotate(p.right)
self.l_rotate(p)
def search(self, value, the_node):
p = the_node
if value > p.value:
if p.right is not None:
x = self.search(value, p.right)
try:
p.r_height = max(x.l_height, x.r_height) + 1
# print(p.value, p.l_height, p.r_height)
self.update_height2(p)
#if abs(p.l_height - p.r_height) >= 2:
self.T_adj(p)
except:
pass
else:
temp = node(value=value, pre=p)
p.right = temp
p.r_height = 1
return p
elif value < p.value:
if p.left is not None:
x = self.search(value, p.left)
try:
# print(x.value)
p.l_height = max(x.l_height, x.r_height) + 1
self.update_height2(p)
#if abs(p.l_height - p.r_height) >= 2:
self.T_adj(p)
except:
pass
else:
temp = node(value=value, pre=p)
p.left = temp
p.l_height = 1
return p
def add(self, value):
self.search(value, self.head)
self.length += 1
# 选用层序
def show_all(self):
print('===========开始==============')
p = self.head
# print("head.value is", self.head.value)
queue =
while len(queue) != 0:
x = queue.pop(0)
print(x.value, x.l_height, x.r_height)
if x.left is not None:
queue.append(x.left)
if x.right is not None:
queue.append(x.right)
print('==========结束===============')
def find(self, key, the_node, direction=''):
p = the_node
if key == p.value:
#print(p.value,direction)
return p, direction
elif p.value < key:
if p.right is not None:
return self.find(key, p.right, 'right')
else:
if p.left is not None:
return self.find(key, p.left, 'left')
def find_min(self, the_node):
if the_node.left is not None:
return self.find_min(the_node.left)
else:
return the_node
def find_max(self, the_node):
if the_node.right is not None:
return self.find_max(the_node.right)
else:
return the_node
def update_height2(self, the_node):
p = the_node
if p is not None:
if p.left is not None and p.right is not None:
p.l_height = max(p.left.l_height,
p.left.r_height) + 1
p.r_height = max(p.right.l_height,
p.right.r_height) + 1
elif p.left is not None and p.right is None:
p.r_height = 0
p.l_height = max(p.left.l_height,
p.left.r_height) + 1
elif p.left is None and p.right is not None:
p.r_height = max(p.right.l_height,
p.right.r_height) + 1
p.l_height = 0
else:
p.r_height = 0
p.l_height = 0
#if max(p.l_height,p.r_height)==0:
self.update_height2(p.pre)
return p
def update_height(self, the_node):
if the_node.left is not None and the_node.right is not None:
the_node.l_height = max(self.update_height(the_node.left).l_height,
self.update_height(the_node.left).r_height) + 1
the_node.r_height = max(self.update_height(the_node.right).l_height,
self.update_height(the_node.right).r_height) + 1
elif the_node.left is not None and the_node.right is None:
the_node.r_height = 0
the_node.l_height = max(self.update_height(the_node.left).l_height,
self.update_height(the_node.left).r_height) + 1
elif the_node.left is None and the_node.right is not None:
the_node.r_height = max(self.update_height(the_node.right).l_height,
self.update_height(the_node.right).r_height) + 1
the_node.l_height = 0
else:
the_node.r_height = 0
the_node.l_height = 0
return the_node
def remove(self, key):
the_node, direction = self.find(key, self.head)
if the_node.left is not None:
replace_max = self.find_max(the_node.left)
else:
replace_max = self.find_max(the_node)
if the_node.right is not None:
replace_min = self.find_min(the_node.right)
else:
replace_min = self.find_max(the_node)
#print(replace_max.value,replace_min.value)
if replace_max.value == replace_min.value == the_node.value:
if direction == 'right':
the_node.pre.right = None
if direction == 'left':
the_node.pre.left = None
self.update_height2(the_node.pre)
the_node = None
elif replace_min.value != the_node.value:
temp = replace_min
temp.pre.left = temp.right
self.update_height2(temp.pre)
temp.right = the_node.right
temp.left = the_node.left
try:
the_node.left.pre = temp
except:
pass
try:
the_node.right.pre = temp
except:
pass
if the_node.value == self.head.value:
temp.pre = None
self.head = temp
else:
temp.pre = the_node.pre
if direction == 'right':
the_node.pre.right = temp
if direction == 'left':
the_node.pre.left = temp
self.update_height2(temp)
self.adj(temp)
the_node = None
elif replace_max.value != the_node.value:
temp = replace_max
temp.pre.right = temp.left
self.update_height2(temp.pre)
temp.left = the_node.left
temp.right = the_node.right
try:
the_node.left.pre = temp
except:
pass
try:
the_node.right.pre = temp
except:
pass
if the_node.value == self.head.value:
temp.pre = None
self.head = temp
else:
temp.pre = the_node.pre
if direction == 'right':
the_node.pre.right = temp
if direction == 'left':
the_node.pre.left = temp
self.update_height2(temp)
self.adj(temp)
the_node = None
self.length -= 1
def l_rotate(self, the_node):
direction = self.find(the_node.value, self.head)
temp = the_node.right
# 把16的左子树要转给12，当12的右子树
the_node.right = temp.left
# 把16的父结点给12
temp.pre = the_node.pre
# 把16变成12的左子结点
temp.left = the_node
# 如果当前结点是头结点，把头结点重新标记成12
if the_node.value == self.head.value:
self.head = temp
else:
# 当前结点不是头结点，说明上面有父结点
# 当前结点16是他父结点的左子结点，把这个关系转给12
if direction == 'left':
the_node.pre.left = temp
else:
the_node.pre.right = temp
# 当前结点16的父结点变成（它的原右子结点）12
the_node.pre = temp
# 更新两个结点的层数
if the_node.right is not None:
the_node.r_height = max(the_node.right.r_height, the_node.right.l_height) + 1
else:
the_node.r_height = 0
self.update_height2(temp)
def r_rotate(self, the_node):
direction = self.find(the_node.value, self.head)
temp = the_node.left
the_node.left = temp.right
temp.pre = the_node.pre
temp.right = the_node
if the_node.value == self.head.value:
self.head = temp
else:
if direction == 'left':
the_node.pre.left = temp
else:
the_node.pre.right = temp
the_node.pre = temp
if the_node.left is not None:
the_node.l_height = max(the_node.left.l_height, the_node.left.r_height) + 1
else:
the_node.l_height = 0
self.update_height2(temp)
def clear_all(self):
self.head=None
self.length-=self.length
def get_len(self):
return self.length
class Window():
def __init__(self):
self.one_link = link(0)
self.root = Tk()
self.root.title('可视化AVL树-作者：lthero')
frame = Frame(self.root, width=Width-20, height=Height-20)
frame.grid(row=0, column=0)
self.canvas = Canvas(frame, bg='#FFFFFF', width=Width-20, height=Height-20, scrollregion=(-800, 0, Width+800, Height+800))#
hbar = Scrollbar(frame, orient=HORIZONTAL)
hbar.pack(side=BOTTOM, fill=X)
hbar.config(command=self.canvas.xview)
vbar = Scrollbar(frame, orient=VERTICAL)
vbar.pack(side=RIGHT, fill=Y)
vbar.config(command=self.canvas.yview)
self.canvas.config(xscrollcommand=hbar.set, yscrollcommand=vbar.set)
self.canvas.pack(side=LEFT, expand=True, fill=BOTH)
self.input_label = ttk.Entry(self.root, font=font.Font(size=13, weight='bold'), width=10)
self.input_label.place(x=10, y=row_0-30)
self.input_label.focus_set()
self.B_in = ttk.Button(self.root, text='add it', command=self.get_int, width=8)
self.B_in.place(x=col_0, y=row_0-30)
self.B_out = ttk.Button(self.root, text='remove it', command=self.delete, width=8)
self.B_out.place(x=col_0, y=row_1-30)
self.B_out = ttk.Button(self.root, text='restart', command=self.restart, width=8)
self.B_out.place(x=col_0-100, y=row_1 - 30)
self.root.bind('<Return>', self.get_int)
self.is_first = 0
screenwidth = self.root.winfo_screenwidth()
screenheight = self.root.winfo_screenheight()
alignstr = '%dx%d+%d+%d' % (Width, Height, (screenwidth - Width) / 2, (screenheight - Height) / 2)
self.root.geometry(alignstr)
def about():
win2 = Toplevel(self.root)
win2.title('关于')
width = 280
height = 200
screenwidth = self.root.winfo_screenwidth()
screenheight = self.root.winfo_screenheight()
alignstr2 = '%dx%d+%d+%d' % (width, height, (screenwidth - width) / 2, (screenheight - height) / 2)
win2.geometry(alignstr2)
win2.resizable(width=False, height=False)
win2.focus_set()
Help = Label(win2, text='可视化AVL树\n\n功能：可以添加，但删除有bug\n\n 完成于2021年4月21日，作者：lthero', font=('微软雅黑', 10))
Help.place(x=40, y=40)
menu = Menu(self.root, tearoff=False)
Cmenu = Menu(menu, tearoff=False)# 新建菜单，删除顶部虚线
Cmenu.add_command(label='关于', command=about)
menu.add_cascade(label='点我', menu=Cmenu)# 实例化菜单
self.root.config(menu=menu)# 实例化菜单
self.root.mainloop()
def restart(self):
self.one_link.clear_all()
self.is_first=0
self.draw_all()
self.input_label.focus_set()
def get_int(self,*args):
x = self.input_label.get()
if self.is_first == 0:
if x != '':
self.add_one(int(x), 1)
self.is_first = 1
else:
if x != '':
self.add_one(int(x))
self.input_label.delete(0,END)
self.input_label.focus_set()
def add_one(self, value, flag=0):
if flag == 1:
self.one_link.head=node(value)
else:
self.one_link.add(value)
self.show()
self.draw_all()
def delete(self):
x = self.input_label.get()
self.one_link.remove(int(x))
self.input_label.delete(0,END)
self.input_label.focus_set()
self.show()
self.draw_all()
def show(self):
self.one_link.show_all()
def draw_one(self,the_node,x,y):
p=the_node
if p is not None:
if p.left is not None:
temp=max(p.left.r_height, p.left.l_height)
pian=30
pian_y=1
if temp>=2:
pian=60
if temp>=3:
pian=80
pian_y+=2
self.canvas.create_line(x, y, x - 30 - temp * pian, y + 35*pian_y)
self.draw_one(p.left, x - 30 - temp * pian, y + 35*pian_y)
if p.right is not None:
temp=max(p.right.l_height, p.right.r_height)
pian=30
pian_y = 1
if temp>=2:
pian=60
if temp>=3:
pian=80
pian_y += 2
self.canvas.create_line(x, y, x +40 + temp * pian, y + 35*pian_y)
self.draw_one(p.right, x + 40 + temp * pian, y + 35*pian_y)
self.canvas.create_oval(x - 15, y - 15, x + 15, y + 15, fill='yellow')
self.canvas.create_text(x, y, text=the_node.value)
else:
return
def draw_all(self):
x = 450
y = 50
if self.one_link.head is not None:
if max(self.one_link.head.r_height,self.one_link.head.l_height)>=3:
x+=150
self.canvas.create_rectangle(-800, 0,Width+800,Height+800, fill='white',width=0)
self.draw_one(self.one_link.head,x,y)
x = Window()
hayyot 发表于 2022-11-22 09:24
大佬大佬！！！这就是算法工程师嘛！！！
在下只是个学生，这是数据结构课的作业啦 tyjjk 发表于 2022-11-23 09:33
记得大学期间data structure是核心课程
是的，数据结构一直挺重要的……不过我学过就忘 牛！！！{:1_921:} 这个厉害，必须学习！ 这个厉害了 这个厉害，必须学习！ 数据结构可视化，之前本科的时候写过类似地，谢谢楼主分享 感谢分享 这个很好，必须支持学习 来学习来打卡，早日成为python大神 非常不错的分享，受教中... 感谢