在 Python 中实现树数据结构

  1. 在 Python 中从头开实现树数据结构
  2. 在 Python 中遍历二叉树
  3. 使用 Python 库实现树

树是数据结构之一。数据结构只是我们如何组织内存中的数据。树是节点(也称为顶点)和边的组合。一棵树可以有任意数量的节点和边。一个节点是我们存储数据的位置,一条边是 2 节点之间的路径。有多种类型的树可用,例如二叉树,三叉树,二叉搜索树,AVL 树等。

Python 中的树

树中节点的类型:

  1. 父节点:具有一个或多个子节点的节点。
  2. 子节点:具有父节点的节点。
  3. 叶子节点:没有任何子节点的节点。

在本文中,我们首先来看如何在不使用任何库的情况下从头开始实现树,然后再看如何在 Python 库的帮助下实现树。

在 Python 中从头开实现树数据结构

要在 Python 中创建树,我们首先必须创建一个表示单个节点的 Node 类。Node 类将包含 3 个变量;第一个是指向左侧子节点的 left 变量,第二个变量是包含该节点值的 data 变量,而第二个变量是指向右侧子节点的 right 变量。

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

让我们初始化一棵树。

root = Node(10)

root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

这棵树如下图所示。

          10
        /    \
       34      89
     /    \ 
    45    50 

每当创建节点类的对象时,都会调用 __init__ 构造函数,并且该构造函数中的所有变量都将被初始化。root 包含树的根节点,该节点的值为 10,以及 root.leftroot.right,我们将使用其插入值 34 的左侧子节点和右侧的子节点。子节点到根节点,其值为 89。由于它是二进制树,因此每个节点最多包含两个节点。

最后,我们在树中再插入两个节点,即 4550,作为节点 34 的子节点。你可以根据要创建的树的类型在树内插入任意数量的节点。

在 Python 中遍历二叉树

现在我们已经创建了一棵树,所以让我们遍历该树以打印树元素。遍历访问树中的每个节点。遍历遍历树中的每个节点三次。我们遍历树的方式是从上到下,从左到右。

前序遍历

在前序遍历树时,每当我们第一次看到该节点时,我们都会打印该节点,然后在左节点然后在右节点上执行递归。

def preorder(node):
    if node:
        print(node.data)
        preorder(node.left)
        preorder(node.right)

输出:

10 
34 
45 
50 
89

中序遍历

在执行中序遍历时,我们首先在左侧节点上执行递归,然后在第二次访问同一节点时,打印该节点。然后,我们在右节点上执行递归。

def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)

输出:

45 
34 
50 
10 
89

后序遍历

对于后序遍历,我们在左节点和右节点上执行递归,然后当我们第三次访问同一节点时,我们将打印该节点。

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data)

输出:

45
50
34
89
10

使用 Python 库实现树

如我们所见,从头开始实现树需要花费一些时间,并且需要大量代码。在 Python 中实现树的更简单方法是使用名为 anytree 的库。anytree 库使你无需编写大量代码即可创建树。

要使用 anytree 库,我们首先必须在以下命令的帮助下进行安装。

pip install anytree

在这里,我们还将创建与先前创建的树相同的树。现在我们可以从 anytree 库中导入 NodeRenderTree

from anytree import Node, RenderTree

root = Node(10)

level_1_child_1 = Node(34, parent=root)
level_1_child_2 = Node(89, parent=root)
level_2_child_1 = Node(45, parent=level_1_child_1)
level_2_child_2 = Node(50, parent=level_1_child_2)

for pre, fill, node in RenderTree(root):
    print("%s%s" % (pre, node.name))
    
# Tree Structure
#          10
#        /    \
#       34      89
#     /    \ 
#    45    50 

输出:

10
├── 34
│   └── 45
└── 89
    └── 50

在这里,Node 将为我们创建一个带有两个参数的节点:第一个是节点的值,第二个是父节点的名称(这是一个可选参数)。由于在我们的树中,root 节点是唯一没有任何父节点的节点,因此在创建 root 节点时,我们将仅传递第一个参数:节点的值,而不传递第二个参数。RenderTree 方法将帮助我们如输出所示打印整个树。