如何获取Python二叉树递归节点的子节点？代码错误排查

核心问题 #

你代码里的totaldict存储的是独立于树结构的新TreeNode实例，和二叉搜索树中实际存在的节点不是同一个对象。比如创建节点5时，你同时做了两件事：

• 给root.left赋值了一个TreeNode(5)实例（这是树里的真实节点）
• 给totaldict[5]赋值了另一个全新的TreeNode(5)实例
  这俩实例完全独立，后续给节点5添加子节点3、7时，修改的是树里那个节点的left/right属性，totaldict里的节点根本没被改动，所以输出自然是None。

解决方案一：去掉全局字典，直接从树中获取节点（推荐） #

二叉搜索树本身具备查找节点的能力，不需要额外用字典存储。修改search方法让它返回找到的节点实例，而不是布尔值，然后直接用这个实例获取子节点：

修改后的完整代码：

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

    def search(self, value):
        if value < self.data:
            if self.left is None:
                return None
            return self.left.search(value)
        elif value > self.data:
            if self.right is None:
                return None
            return self.right.search(value)
        else:
            return self  # 返回当前找到的节点实例

    def create_node(self, value):
        if value < self.data:
            if self.left is None:
                self.left = TreeNode(value)
            else:
                self.left.create_node(value)
        elif value > self.data:
            if self.right is None:
                self.right = TreeNode(value)
            else:
                self.right.create_node(value)
        else:
            print("Node already exists")

    def pos_child(self, value):
        node = self.search(value)
        if node:
            # 子节点存在则取data，否则显示None
            left_child = node.left.data if node.left else None
            right_child = node.right.data if node.right else None
            return f"Left child: {left_child} Right Child: {right_child}"
        else:
            print("Node does not exist, use create_node method")


root = TreeNode(10)
root.create_node(5)
root.create_node(15)
root.create_node(3)
root.create_node(7)

print(root.pos_child(5))  # 输出：Left child: 3 Right Child: 7

解决方案二：保留字典，但确保存储的是树中真实节点 #

如果你一定要用totaldict，那要保证字典里存的是树中实际创建的节点实例，而不是每次新建一个：

修改create_node方法中的字典赋值逻辑：

totaldict = {}
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def search(self, value):
        if value < self.data:
            if self.left == None:
                return False
            else:
                return self.left.search(value)
        elif value > self.data:
            if self.right == None:
                return False
            else:
                return self.right.search(value)
        else:
            return True

    def create_node(self, value):
        if value < self.data:
            if self.left is None:
                new_node = TreeNode(value)
                self.left = new_node
                totaldict[value] = new_node  # 存入树中刚创建的节点，而非新实例
            else:
                self.left.create_node(value)
        elif value > self.data:
            if self.right is None:
                new_node = TreeNode(value)
                self.right = new_node
                totaldict[value] = new_node
            else:
                self.right.create_node(value)
        else:
            print("Node already exists")

    def pos_child(self, value):
        if self.search(value):
            if value in totaldict:
                left_data = totaldict[value].left.data if totaldict[value].left else None
                right_data = totaldict[value].right.data if totaldict[value].right else None
                return f"Left child: {left_data} Right Child: {right_data}"
        else:
            print("Node does not exist, use create_node method")


root = TreeNode(10)
root.create_node(5)
root.create_node(15)
root.create_node(3)
root.create_node(7)

print(root.pos_child(5))  # 输出：Left child: 3 Right Child: 7

这样totaldict里的节点和树中的节点是同一个对象，后续修改子节点时字典里的节点也会同步更新。

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