【AVL树】python实现动态可视化

Lthero

最近复习数据结构，翻出快一年前写的代码……感慨当时好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

代码

[Python] 纯文本查看 复制代码

?

001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436

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 = [p]         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)[1]         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)[1]         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()

Lthero

hayyot 发表于 2022-11-22 09:24
大佬大佬！！！这就是算法工程师嘛！！！

在下只是个学生，这是数据结构课的作业啦

Lthero

tyjjk 发表于 2022-11-23 09:33
记得大学期间data structure是核心课程

是的，数据结构一直挺重要的……不过我学过就忘

天真Aro

牛！！！

XJCQ2014

这个厉害，必须学习！

ztscope

这个厉害了

QQ12349qq

这个厉害，必须学习！

lhp462

数据结构可视化，之前本科的时候写过类似地，谢谢楼主分享

yyb414

感谢分享

chujian2021

这个很好，必须支持学习

bj9ye666

来学习来打卡，早日成为python大神

Gijia

非常不错的分享，受教中... 感谢