Python二叉树实现与解析

学习文章要努力，但是不要急！今天的这篇文章《Python实现二叉树详解》将会介绍到等等知识点，如果你想深入学习文章，可以关注我！我会持续更新相关文章的，希望对大家都能有所帮助！

如何构建一个基本的二叉树节点？明确答案是定义一个包含值和左右子节点引用的Python类。具体做法是创建一个TreeNode类，其__init__方法接收val（节点值）、left（左子节点引用）和right（右子节点引用）三个参数，并将它们分别赋值给实例属性；2. Python中常见的二叉树遍历方式有哪些？明确答案是前序、中序和后序三种遍历方式。前序遍历先访问根节点，再递归遍历左子树和右子树；中序遍历先递归遍历左子树，再访问根节点，最后递归遍历右子树；后序遍历先递归遍历左子树和右子树，最后访问根节点；3. 如何在二叉搜索树中插入和删除节点？明确答案是插入通过递归查找合适位置实现，删除则根据节点情况分别处理。插入操作从根节点开始，若新值小于当前节点则进入左子树递归插入，否则进入右子树递归插入；删除操作分为三种情况：若为叶子节点直接删除，若只有一个子节点则用子节点替代，若有两个子节点则选择右子树中最小节点或左子树中最大节点作为替代者并递归删除该替代节点。

Python实现二叉树，说白了，核心就是定义一个节点（Node），然后通过这个节点来管理它左右子节点的引用关系。这玩意儿本质上是递归思想的体现，用Python的类和对象来模拟那种层级结构，既直观又灵活。它不像数组那样连续存储，而是靠指针（在Python里就是对象引用）把散落在内存各处的节点串起来。

解决方案

要搞定二叉树，我们通常会先定义一个节点类，然后在此基础上构建树的操作逻辑。

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

    def __repr__(self):
        # 只是为了方便打印和调试，实际使用中可能不需要
        return f"Node({self.val})"

# 构建一个简单的二叉树（非二叉搜索树）
# 根节点
root = TreeNode(1)
# 左子树
root.left = TreeNode(2)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 右子树
root.right = TreeNode(3)
root.right.left = TreeNode(6)

print("二叉树节点已构建。")

# 接下来是遍历，这是理解树结构最直接的方式
def inorder_traversal(node):
    """中序遍历：左 -> 根 -> 右"""
    if node:
        inorder_traversal(node.left)
        print(node.val, end=" ")
        inorder_traversal(node.right)

print("中序遍历结果：")
inorder_traversal(root)
print("\n") # 换行

def preorder_traversal(node):
    """前序遍历：根 -> 左 -> 右"""
    if node:
        print(node.val, end=" ")
        preorder_traversal(node.left)
        preorder_traversal(node.right)

print("前序遍历结果：")
preorder_traversal(root)
print("\n")

def postorder_traversal(node):
    """后序遍历：左 -> 右 -> 根"""
    if node:
        postorder_traversal(node.left)
        postorder_traversal(node.right)
        print(node.val, end=" ")

print("后序遍历结果：")
postorder_traversal(root)
print("\n")

如何构建一个基本的二叉树节点？

构建一个二叉树节点，说白了就是定义一个Python类。我个人觉得，这玩意儿是所有树结构操作的基石，没有它，你连树的影子都摸不着。这个类通常包含三个核心属性：一个用于存储节点值（val），另外两个则是指向其左子节点和右子节点的引用（left和right）。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        """
        初始化一个二叉树节点。
        :param val: 节点存储的值。可以是任何类型，数字、字符串、甚至其他对象。
        :param left: 指向左子节点的引用。如果当前没有左子节点，通常设为None。
        :param right: 指向右子节点的引用。如果当前没有右子节点，通常设为None。
        """
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        # 这个方法是为了方便调试，当你直接打印一个TreeNode对象时，它会显示这个格式。
        # 比如 print(TreeNode(5)) 会输出 Node(5)
        return f"Node({self.val})"

# 举个例子，看看怎么用它：
node_a = TreeNode(10) # 创建一个值为10的节点，此时它没有左右子节点
node_b = TreeNode(20)
node_c = TreeNode(30)

node_a.left = node_b # 把node_b设为node_a的左子节点
node_a.right = node_c # 把node_c设为node_a的右子节点

# 现在，node_a 就是一个根节点，node_b是它的左孩子，node_c是它的右孩子。
# 我们可以这样访问：
print(f"根节点的值: {node_a.val}")
print(f"根节点的左孩子值: {node_a.left.val}")
print(f"根节点的右孩子值: {node_a.right.val}")
# 如果尝试访问一个不存在的子节点，比如 node_b.left，它会是None。

这里面的left和right属性，它们存储的不是值本身，而是指向另一个TreeNode对象的内存地址（或者说引用）。这就跟搭积木似的，你把一块积木（节点）放在那儿，然后用线（引用）把它和另一块积木连接起来。如果没连接，那线就是空的（None）。这种设计让树的结构变得非常灵活，可以动态地增删节点，而不用像数组那样担心内存连续性或扩容问题。

Python中常见的二叉树遍历方式有哪些？

二叉树的遍历，简单来说，就是按照某种特定的顺序访问树中的每一个节点。这事儿在数据结构里挺重要的，因为很多时候你需要把树里的所有数据都过一遍，或者按特定逻辑找出某个数据。常见的遍历方式有三种，它们都基于递归思想，但访问节点的顺序不同：前序、中序和后序。

1. 前序遍历 (Pre-order Traversal)：

   • 访问根节点。
   • 递归遍历左子树。
   • 递归遍历右子树。
   • 这种遍历方式，我觉得挺像我们平时看目录结构，先看当前文件夹的名字，再看它里面的子文件夹。

   def preorder_traversal(node):
       if node:
           print(node.val, end=" ")  # 先访问根节点
           preorder_traversal(node.left)  # 再遍历左子树
           preorder_traversal(node.right) # 最后遍历右子树

2. 中序遍历 (In-order Traversal)：

   • 递归遍历左子树。
   • 访问根节点。
   • 递归遍历右子树。
   • 中序遍历在二叉搜索树（BST）里特别有用，因为它能按升序（或降序）访问所有节点。这对我来说，是它最直观的用途之一。

   def inorder_traversal(node):
       if node:
           inorder_traversal(node.left)   # 先遍历左子树
           print(node.val, end=" ")   # 再访问根节点
           inorder_traversal(node.right)  # 最后遍历右子树

3. 后序遍历 (Post-order Traversal)：

   • 递归遍历左子树。
   • 递归遍历右子树。
   • 访问根节点。
   • 后序遍历的一个典型应用是计算表达式树的值，或者在删除树时，先删除子节点再删除父节点，避免悬空指针。

   def postorder_traversal(node):
       if node:
           postorder_traversal(node.left)  # 先遍历左子树
           postorder_traversal(node.right) # 再遍历右子树
           print(node.val, end=" ")  # 最后访问根节点

除了递归，这三种遍历方式也可以用迭代的方式实现，通常需要借助栈来模拟递归的调用栈。迭代实现虽然代码量可能多一些，但可以避免深度递归带来的栈溢出风险，尤其是在处理非常深的树时，这会是个实际的考量。

如何在二叉搜索树中插入和删除节点？

这里我们特指二叉搜索树 (Binary Search Tree, BST)，因为在普通二叉树中，插入和删除通常没有固定的规则，可以任意位置插入或删除，这取决于具体的应用场景。但在BST中，每个节点的值都大于其左子树中任意节点的值，且小于其右子树中任意节点的值。这个特性让插入和删除变得有章可循，但也更复杂。

插入节点：

插入一个新节点到BST，其实就是找到它应该待的那个“坑”。这个过程是个递归的查找，从根节点开始：

• 如果新值比当前节点小，就往左子树找。
• 如果新值比当前节点大，就往右子树找。
• 直到找到一个空位置（None），就把新节点放进去。

def insert_bst(root, val):
    if root is None:
        return TreeNode(val) # 如果树是空的，新节点就是根节点

    if val < root.val:
        root.left = insert_bst(root.left, val) # 往左子树递归插入
    else: # 假设没有重复值，或者重复值放在右边
        root.right = insert_bst(root.right, val) # 往右子树递归插入
    return root # 返回当前子树的根节点

删除节点：

删除节点是BST操作里最麻烦的一个，因为它分好几种情况，得小心翼翼地处理，不然树的结构就乱了。我个人觉得，理解这块儿需要多画图，才能把逻辑搞清楚。

删除一个节点node_to_delete，主要有三种情况：

1. node_to_delete 是叶子节点 (没有子节点)： 直接删除它，也就是将其父节点指向它的引用设为None。这是最简单的情况。

2. node_to_delete 只有一个子节点： 用它的那个唯一的子节点来替代它。比如，如果它只有左子节点，就把左子节点提上来；如果只有右子节点，就把右子节点提上来。

3. node_to_delete 有两个子节点： 这是最复杂的情况。我们需要找到一个“替代者”来填补被删除节点的位置，并且这个替代者要能维持BST的特性。通常有两种选择：

   • 右子树中最小的节点 (in-order successor)： 找到被删除节点右子树中值最小的节点，用它的值替换被删除节点的值，然后递归地删除这个最小节点（它肯定没有左子节点，可能是叶子或只有一个右子节点）。
   • 左子树中最大的节点 (in-order predecessor)： 找到被删除节点左子树中值最大的节点，用它的值替换被删除节点的值，然后递归地删除这个最大节点。

下面是一个简化的删除逻辑，主要展示了处理这三种情况的思路：

def find_min_node(node):
    """辅助函数：找到子树中值最小的节点"""
    current = node
    while current.left is not None:
        current = current.left
    return current

def delete_bst(root, val):
    if root is None:
        return root # 树为空，或者没找到要删除的节点

    # 递归查找要删除的节点
    if val < root.val:
        root.left = delete_bst(root.left, val)
    elif val > root.val:
        root.right = delete_bst(root.right, val)
    else: # 找到了要删除的节点 (root.val == val)
        # 情况 1 & 2: 节点只有一个子节点或没有子节点
        if root.left is None:
            return root.right # 直接返回右子节点（可能是None）
        elif root.right is None:
            return root.left # 直接返回左子节点

        # 情况 3: 节点有两个子节点
        # 找到右子树中最小的节点 (in-order successor)
        temp = find_min_node(root.right)
        # 用这个最小节点的值替换当前节点的值
        root.val = temp.val
        # 递归地删除右子树中的那个最小节点
        root.right = delete_bst(root.right, temp.val)

    return root

删除操作的实现往往比较考验对递归和指针操作的理解。特别是处理有两个子节点的情况，需要先找到合适的替代者，再把那个替代者从原来的位置“挖”出来，这个过程如果逻辑不清晰，很容易出错。实际编码时，通常会写一些辅助函数来让代码更清晰，比如上面那个find_min_node。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。