创建二叉树 二叉树如何删除节点操作教程

创建二叉树

要创建一颗二叉树，可以使用节点类（node class）来定义一个节点。每个节点对象包含了存储的值和指向左右子树的指针。下面是一个示例的节点类：

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

接着，我们就可以通过节点类来定义一颗二叉树了。例如，下面的代码创建了一颗包含三个节点的二叉树：

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

这棵树的结构如下所示：

    1
   / \
  2   3

我们可以按照同样的方式来添加更多的节点，以创建一整颗二叉树。下面是一个示例程序，展示了如何创建一颗包含七个节点的完整二叉树：

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)

这棵树的结构如下所示：

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

二叉树如何删除节点操作教程

删除叶子节点

要删除二叉树中的一个节点，首先需要找到这个节点。找到后，我们需要处理三种不同的情况。第一种情况是删除叶子节点（即没有左右子树的节点）。对于这种情况，我们只需要将父节点中指向该节点的指针设为None即可。

例如，下面是一个示例的二叉树，我们要删除节点6：

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

我们先找到要删除的节点6，然后修改它的父节点中的指针：

def delete_node(root, value):
    # 找到要删除的节点
    node = find_node(root, value)
    # 如果要删除的是根节点
    if node == root:
        root = None
    # 如果要删除的是叶子节点
    elif node.left is None and node.right is None:
        parent = find_parent(root, node)
        if parent.left == node:
            parent.left = None
        else:
            parent.right = None

在上面的代码中，我们使用了两个辅助函数find_node和find_parent。其中find_node函数用于在二叉树中查找某个节点，而find_parent函数则用于查找某个节点的父节点。这两个函数的实现可以根据具体需求来编写。

删除有一个子节点的节点

第二种情况是删除有一个子节点的节点。对于这种情况，我们只需要将父节点中指向该节点的指针，修改为指向该节点的子节点即可。

例如，下面的示例二叉树，我们要删除节点2：

       1
     /   \
    2     3
         / \
        6   7

我们先找到要删除的节点2，然后修改它的父节点中的指针：

def delete_node(root, value):
    # 找到要删除的节点
    node = find_node(root, value)
    # 如果要删除的是根节点
    if node == root:
        root = None
    # 如果要删除的是叶子节点
    elif node.left is None and node.right is None:
        parent = find_parent(root, node)
        if parent.left == node:
            parent.left = None
        else:
            parent.right = None
    # 如果要删除的节点有一个子节点
    elif node.left is None:
        parent = find_parent(root, node)
        if parent.left == node:
            parent.left = node.right
        else:
            parent.right = node.right
    elif node.right is None:
        parent = find_parent(root, node)
        if parent.left == node:
            parent.left = node.left
        else:
            parent.right = node.left

在上面的代码中，我们分别处理了节点只有左子树、只有右子树的情况。如果节点有左右子树，我们可以选择指向左子树或右子树中的一个节点，具体选择哪个节点，可以根据具体的需求来决定。

删除有两个子节点的节点

第三种情况是删除有两个子节点的节点。这种情况比较复杂，需要使用一些特殊的算法来处理。一个常用的算法是“取代法”（replace method），即用当前节点的左子树当中的最大节点或右子树当中的最小节点来取代它。

例如，下面的示例二叉树，我们要删除节点2：

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

我们先找到要删除的节点2。接着，我们可以用节点2左子树当中的最大节点5来取代它。具体操作是，将节点5移动到节点2的位置，并将节点5的值赋给节点2。

       1
     /   \
    5     3
   /     / \
  4     6   7

这样，我们就成功地删除了节点2，并保持了二叉树的平衡。

下面是实现“取代法”删除节点的示例代码。其中，find_largest函数用于查找节点左子树当中的最大值，find_smallest函数则用于查找节点右子树当中的最小值。

def delete_node(root, value):
    # 找到要删除的节点
    node = find_node(root, value)
    # 如果要删除的是根节点
    if node == root:
        root = None
    # 如果要删除的是叶子节点
    elif node.left is None and node.right is None:
        parent = find_parent(root, node)
        if parent.left == node:
            parent.left = None
        else:
            parent.right = None
    # 如果要删除的节点有一个子节点
    elif node.left is None:
        parent = find_parent(root, node)
        if parent.left == node:
            parent.left = node.right
        else:
            parent.right = node.right
    elif node.right is None:
        parent = find_parent(root, node)
        if parent.left == node:
            parent.left = node.left
        else:
            parent.right = node.left
    # 如果要删除的节点有两个子节点
    else:
        # 查找左子树当中的最大值
        largest = find_largest(node.left)
        # 将最大值节点移动到当前节点的位置
        node.value = largest.value
        # 删除左子树当中的最大值节点
        delete_node(node.left, largest.value)

def find_largest(node):
    while node.right is not None:
        node = node.right
    return node

def find_smallest(node):
    while node.left is not None:
        node = node.left
    return node

至此，我们已经完成了二叉树的删除节点操作的教程，希望能够对你有所帮助。