Python二叉树结构修复请求：遍历结果不符合预期

问题原因分析 #

1. 构造函数错误：Python类的构造函数必须是__init__（双下划线），原代码写成init，导致节点初始化逻辑失效。
2. 遍历方法逻辑错误：原遍历方法通过传入root参数并使用self调用递归，导致递归过程中始终以初始根节点为上下文，无法正确遍历子节点。
3. 树结构不符合预期：原代码使用二叉搜索树的insert方法自动按字母顺序构建树，但需要的是特定结构的二叉树来得到预期遍历结果，自动插入无法生成目标结构。

修复步骤与代码 #

1. 修正构造函数 #

将def init(self, data):改为def __init__(self, data):，确保节点能正确初始化左右子树和数据。

2. 修正遍历方法 #

重构遍历方法，去掉冗余的root参数，直接通过self的左右子树递归：

• 中序遍历：左子树 → 根 → 右子树
• 前序遍历：根 → 左子树 → 右子树

3. 手动构建目标树结构 #

结合预期的前序（EXAMFUN）和中序（MAFXUEN）遍历结果，推导树结构并手动创建节点关系，替代自动插入逻辑。

完整修复代码 #

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

    # 中序遍历：Left -> Root -> Right
    def inorderTraversal(self):
        res = []
        if self.left:
            res += self.left.inorderTraversal()
        res.append(self.data)
        if self.right:
            res += self.right.inorderTraversal()
        return res

    # 前序遍历：Root -> Left -> Right
    def preorderTraversal(self):
        res = []
        res.append(self.data)
        if self.left:
            res += self.left.preorderTraversal()
        if self.right:
            res += self.right.preorderTraversal()
        return res

# 手动构建目标二叉树
root = Node('E')
# E的左子树是X，右子树是N
root.left = Node('X')
root.right = Node('N')
# X的左子树是A，右子树是U
root.left.left = Node('A')
root.left.right = Node('U')
# A的左子树是M，右子树是F
root.left.left.left = Node('M')
root.left.left.right = Node('F')

# 输出遍历结果
print('In-Order:\t', ''.join(root.inorderTraversal()))
print('Pre-Order:\t', ''.join(root.preorderTraversal()))

验证结果 #

运行修复后的代码，输出将符合预期：

In-Order: MAFXUEN
Pre-Order: EXAMFUN

内容的提问来源于stack exchange，提问作者cswanepoel