在 Python 中实现树数据结构

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

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

树中节点的类型：

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 

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

最后，我们在树中再插入两个节点，即 45 和 50，作为节点 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 库中导入 Node 和 RenderTree。

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 方法将帮助我们如输出所示打印整个树。