Python程序构建树并执行插入、删除、显示操作

本文将介绍如何使用Python编写程序来构建一棵树，并实现常用的插入、删除、显示等操作。

什么是树？

树是一种以分层方式组织数据的数据结构，通常用于处理具有层级关系的数据。例如，在计算机科学中，文件系统和网站地图都是树的常见应用场景。

树的基本组成部分包括根节点、节点和边。根节点是树的顶部节点，没有父节点。节点是树中的元素，每一个节点包含一个值和指向其他节点的指针。边是连接两个节点的线。

下面是一个简单的树的例子：

          1
       /     \
      2       3
     / \     / \
    4   5   6   7

在这个例子中，数字表示节点的值，并且每个节点包含两个子节点指针（除叶子节点之外）。节点1是树的根节点。

构建树

在Python中可以使用类来表示树。每个节点是一个类的实例，该类包含一个值和左/右子节点的指针。

下面是一个简单的节点类：

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

我们可以使用上面的节点类来创建一颗树。为了方便，我们创建一个树类，该类包含根节点的指针。

class Tree:
    def __init__(self, root=None):
        self.root = root

现在我们将创建上述树的示例。首先，我们创建根节点，并为它添加左右子节点：

root = Node(1)
root.left = Node(2)
root.right = Node(3)

然后，为每个子节点添加两个子节点：

root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

现在我们已经创建了这棵树，我们可以开始实现插入、删除和显示操作。

插入操作

插入操作将新节点添加到树中。要插入节点，我们需要遍历树以找到正确的位置。我们将从根节点开始，并向下遍历，直到找到适当的位置。

下面是一个插入新节点的函数：

def insert_node(node, val):
    if node is None:
        return Node(val)
    if val < node.val:
        node.left = insert_node(node.left, val)
    else:
        node.right = insert_node(node.right, val)
    return node

该函数需要两个参数。第一个参数是要遍历的节点，第二个参数是要插入的节点的值。

如果节点为空，则创建新节点，并且将新节点返回。否则，比较当前节点的值和要插入的值。如果要插入的值小于当前节点的值，则我们遍历左子树并添加新节点。否则，我们遍历右子树并添加新节点。

为了插入一个新节点，我们可以调用上述函数，并将根节点和要插入的节点的值作为参数传递。

root = insert_node(root, 8)

删除操作

删除操作将节点从树中删除。要删除节点，我们需要遍历树以找到要删除的节点，并从树中删除它。

下面是一个删除节点的函数：

def delete_node(node, val):
    if node is None:
        return None
    if val < node.val:
        node.left = delete_node(node.left, val)
    elif val > node.val:
        node.right = delete_node(node.right, val)
    else:
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        else:
            temp = node.right
            while temp.left is not None:
                temp = temp.left
            node.val = temp.val
            node.right = delete_node(node.right, temp.val)
    return node

该函数需要两个参数。第一个参数是要遍历的节点，第二个参数是要删除的节点的值。

如果节点为空，则返回None。否则，比较当前节点的值和要删除的值。如果要删除的值小于当前节点的值，则我们遍历左子树并删除节点。如果要删除的值大于当前节点的值，则我们遍历右子树并删除节点。否则，我们找到要删除的节点。

如果要删除的节点没有左子节点，则我们将其右子节点提升到当前位置。如果要删除的节点没有右子节点，则我们将其左子节点提升到当前位置。否则，我们找到右子树中最小值的节点，并将它的值替换为当前节点。然后，我们继续遍历右子树并删除节点。

为了删除一个节点，我们可以调用上述函数，并将根节点和要删除的节点的值作为参数传递。

root = delete_node(root, 4)

显示操作

显示操作将树打印到屏幕上。要显示树，我们需要按层遍历树，并在每个级别上打印节点的值。

下面是一个显示树的函数：

from collections import deque

def print_tree(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            print(node.val, end=' ')
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        print()

该函数需要一个参数，该参数是根节点。我们使用双端队列来存储需要打印的节点。我们首先将根节点放入队列中，然后开始遍历队列。在每个级别上，我们打印每个节点的值，并将其子节点添加到队列中。然后，我们打印一个换行符来分隔不同的级别。

为了打印树，我们可以调用上述函数，并将根节点作为参数传递。

print_tree(root)

完整代码

下面是使用节点类、树类、插入、删除和显示操作的完整示例代码：

from collections import deque

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

class Tree:
    def __init__(self, root=None):
        self.root = root

def insert_node(node, val):
    if node is None:
        return Node(val)
    if val < node.val:
        node.left = insert_node(node.left, val)
    else:
        node.right = insert_node(node.right, val)
    return node

def delete_node(node, val):
    if node is None:
        return None
    if val < node.val:
        node.left = delete_node(node.left, val)
    elif val > node.val:
        node.right = delete_node(node.right, val)
    else:
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        else:
            temp = node.right
            while temp.left is not None:
                temp = temp.left
            node.val = temp.val
            node.right = delete_node(node.right, temp.val)
    return node

def print_tree(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            print(node.val, end=' ')
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        print()

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

root= insert_node(root, 8)
root = delete_node(root, 4)
print_tree(root)

输出结果：