如何基于用户输入在二叉树中每次单步移动一个节点实现遍历

原有代码问题 #

• 草稿逻辑是遍历预设的节点列表，没有真正关联二叉树的父子节点关系，无法根据树结构动态移动
• 原有Node类的insert方法是排序二叉树的数值比较逻辑，不适用于20问的自定义问题树结构
• 硬编码endNode列表维护成本高，可通过判断节点是否为叶子节点自动终止

完整实现代码 #

class Node:
    def __init__(self, data):
        self.left = None  # 对应回答no的路径
        self.right = None # 对应回答yes的路径
        self.data = data  # 节点存储的内容，非叶子节点为问题，叶子节点为答案

# 手动构建20问二叉树示例，可根据需求自定义节点和关联关系
def build_question_tree():
    # 根节点（第一层问题）
    root = Node("它是动物吗？")
    # 第二层节点
    root.left = Node("它是植物吗？") # 回答no的路径
    root.right = Node("它有四条腿吗？") # 回答yes的路径
    # 第三层节点
    root.left.left = Node("它是日常用品吗？")
    root.left.right = Node("它会开花吗？")
    root.right.left = Node("它生活在水里吗？")
    root.right.right = Node("它会喵喵叫吗？")
    # 第四层叶子节点（答案）
    root.left.left.left = Node("石头")
    root.left.left.right = Node("杯子")
    root.left.right.left = Node("绿萝")
    root.left.right.right = Node("玫瑰")
    root.right.left.left = Node("金鱼")
    root.right.right.left = Node("狗")
    root.right.right.right = Node("猫")
    return root

def interactive_traverse(root):
    current_node = root
    # 只要当前节点不是叶子节点，就继续提问
    while current_node.left is not None and current_node.right is not None:
        print(f"\n当前问题：{current_node.data}")
        # 输入校验
        while True:
            user_input = input("请输入y（是）/n（否）：").strip().lower()
            if user_input in ('y', 'n'):
                break
            print("输入无效，请重新输入")
        # 根据输入移动节点
        if user_input == 'y':
            current_node = current_node.right
        else:
            current_node = current_node.left
    # 跳出循环说明到达答案节点
    print(f"\n最终答案：{current_node.data}")

if __name__ == "__main__":
    question_tree = build_question_tree()
    print("欢迎来到20问游戏！")
    interactive_traverse(question_tree)

功能说明 #

• 节点逻辑：非叶子节点存储问题，叶子节点存储最终答案
• 移动规则：用户回答y（是）则移动到右子节点，回答n（否）则移动到左子节点，每次仅移动一个节点
• 终止逻辑：自动判断当前节点是否为叶子节点，无需手动维护终止节点列表
• 可扩展性：修改build_question_tree方法即可自定义问题路径和答案，适配不同的20问场景

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