在 Python 中实现树数据结构

Sahil Bhosale 2024年2月15日
  1. 在 Python 中从头开实现树数据结构
  2. 在 Python 中遍历二叉树
  3. 使用 Python 库实现树
在 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 

每当创建 Node 类的对象时,都会调用 __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 方法将帮助我们如输出所示打印整个树。

作者: Sahil Bhosale
Sahil Bhosale avatar Sahil Bhosale avatar

Sahil is a full-stack developer who loves to build software. He likes to share his knowledge by writing technical articles and helping clients by working with them as freelance software engineer and technical writer on Upwork.

LinkedIn

相关文章 - Python Data Structure