在 Python 中实现数据结构之树
树是数据结构之一。数据结构只是我们如何组织内存中的数据。树是节点（也称为顶点）和边的组合。一棵树可以有任意数量的节点和边。一个节点是我们存储数据的位置，一条边是 2 节点之间的路径。有多种类型的树可用，例如二叉树，三叉树，二叉搜索树，AVL 树等。
树中节点的类型：
- 父节点：具有一个或多个子节点的节点。
- 子节点：具有父节点的节点。
- 叶子节点：没有任何子节点的节点。
在本文中，我们首先来看如何在不使用任何库的情况下从头开始实现树，然后再看如何在 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 方法将帮助我们如输出所示打印整个树。
