使用 Python、Tkinter 和 Graphviz 可视化二叉搜索树

• 下载源代码 - 1.1 KB

引言

本文演示了如何向二叉搜索树添加节点、遍历节点，以及使用 Python 和 Tkinter 在 GUI 环境中可视化树。

背景

树数据结构是一种非线性数据结构，因为它不按顺序存储数据。它被称为分层结构，因为数据以多个级别排列在树中。 在树中，最顶层的节点称为根节点。 每个节点包含一些数据，这些数据可以是任何类型，以及指向其他节点（称为子节点）的地址。

以下是一些与树相关的术语

1. 根：它是树中最顶端的节点。它没有任何父节点。
2. 子节点：它是某个节点的后代。
3. 父节点：它是具有子节点（子节点）的节点。
4. 兄弟节点：它们是拥有共同（相同）父节点的子节点。
5. 叶节点：它是不具有子节点的节点。 它是最底层的节点。它也称为外部节点。
6. 内部节点：它是至少有一个子节点的节点。
7. 祖先节点：它是从根到当前节点的路径上的前驱节点。
8. 后代节点：它是任何节点的直接后继节点。

二叉搜索树是一种特殊的树，其中每个节点最多可以有两个子节点，并且左子树中每个节点的值必须小于根节点的值，右子树中每个节点的值必须大于根节点的值。

二叉搜索树中的节点包含三个字段

1. 数据字段
2. 左子节点地址字段
3. 右子节点地址字段

节点遍历

二叉搜索树中的节点可以通过三种方式遍历

（所有遍历函数都是递归函数）

1. 中序 - 左-根-右
   • 遍历左子树。
   • 访问根。
   • 遍历右子树。
2. 先序 - 根-左-右
   • 访问根。
   • 遍历左子树。
   • 遍历右子树。
3. 后序 - 左-右-根
   • 遍历左子树。
   • 遍历右子树。
   • 访问根。

Using the Code

该应用程序是一个基于 Tkinter 的 GUI 应用程序，用户可以在其中输入数据并实时可视化它。

可以使用 node 类来描述二叉搜索树的节点，如下所示

class Node:
    def __init__(self,data):
         self.data = data
         self.left = None
         self.right = None

插入和遍历操作在 Tree 类中定义如下

class Tree:
    def __init__(self):
        self.root = None
        self.nodes = ""
    def addnode(self,data):
        currnode = Node(data)
        if self.root is None:
            self.root = currnode
        else:
            parent = None
            ptr = self.root
            while ptr is not None:
                parent = ptr
                if int(currnode.data) < int(ptr.data):
                    ptr = ptr.left
                else:
                    ptr = ptr.right
            if int(currnode.data) < int(parent.data):
                parent.left = currnode
            else:
                parent.right = currnode
    def inorder(self,root):
            if root != None:
                self.inorder(root.left)
                self.nodes += root.data + " "
                self.inorder(root.right)
    def preorder(self,root):
            if root != None:
                self.nodes += root.data + " "
                self.preorder(root.left)
                self.preorder(root.right)
    def postorder(self,root):
            if root != None:
                self.postorder(root.left)
                self.postorder(root.right)
                self.nodes += root.data + " "
    def visualizetree(self,root):
        dot = graphviz.Digraph()
        dot.node(str(root.data))
        self.addedge(root,dot)
        dot.render("tree",format="png")
    def addedge(self,node,dot):
        if node.left:
            dot.node(str(node.left.data))
            dot.edge(str(node.data),str(node.left.data))
            self.addedge(node.left,dot)
        if node.right:
            dot.node(str(node.right.data))
            dot.edge(str(node.data),str(node.right.data))
            self.addedge(node.right,dot)

在上面的代码中，addnode() 函数根据节点的值将其添加到树中的适当位置。 inorder()、preorder() 和 postorder() 递归函数执行相应的遍历，并将遍历的节点值存储在 nodes 变量中。 visualizetree() 方法使用 graphviz 执行可视化。 addedge() 函数递归地绘制从节点到其子节点的边。 树被渲染并作为“png”图像存储在当前文件夹中。

以下代码提供了应用程序的 GUI 环境

def add():
    tree.addnode(txtvalue.get())
    tree.visualizetree(tree.root)
    img = ImageTk.PhotoImage(Image.open("tree.png"))
    lblimage.configure(image=img)
    lblimage.image = img

def inorder():
    tree.inorder(tree.root)
    messagebox.showinfo("Inorder",tree.nodes)
    tree.nodes = ""

def preorder():
    tree.preorder(tree.root)
    messagebox.showinfo("Preorder",tree.nodes)
    tree.nodes = ""

def postorder():
    tree.postorder(tree.root)
    messagebox.showinfo("Postorder",tree.nodes)
    tree.nodes = ""

def showimage(event):
    os.system("tree.png") if os.path.exists("tree.png") else None

if __name__ == "__main__":

    tree = Tree()
    root = Tk()
    root.title("Binary Search Tree")
    root.geometry("500x300")

    lblvalue = Label(root,text="Enter data: ")
    lblvalue.place(x=50,y=50,width=100)

    txtvalue = Entry(root)
    txtvalue.place(x=150,y=50,width=100)

    btnadd = Button(root,text="Add",command=add)
    btnadd.place(x=50,y=100,width=100)

    btninorder = Button(root,text="Inorder",command=inorder)
    btninorder.place(x=150,y=100,width=100)

    btnpreorder = Button(root,text="Preorder",command=preorder)
    btnpreorder.place(x=50,y=150,width=100)

    btnpostorder = Button(root,text="Postorder",command=postorder)
    btnpostorder.place(x=150,y=150,width=100)

    lblimage = Label(root)
    lblimage.bind("<Button-1>",showimage)
    lblimage.place(x=300,y=50,width=150,height=150)
    root.mainloop()

    if os.path.exists("tree.png"):
       os.remove("tree.png")
       os.remove("tree")

上面的代码可用于添加节点并以交互方式可视化树。 渲染后的树显示在标签中，单击该标签会在默认图像查看器应用程序中打开树图像。

关注点

我希望读者觉得这篇文章及其概念有用。

历史

• 2024 年 2 月 21 日：初始版本