递归无法返回上一指针？二叉搜索树版20问游戏构建遇阻

Hey there! Let’s break down your problem step by step—building a 20 Questions game with a BST is a fun project, and you’re stuck on two key parts: parsing that text file into the tree correctly, and handling navigation back to previous nodes when using recursion. Let’s tackle each one.

1. Parsing the Text File into a BST #

First, let’s clarify your file format: lines starting with * are leaf nodes (answers), and other lines are question nodes (non-leaf, with "yes"/"no" branches). Based on the example you shared, it looks like your file uses a level-order (breadth-first) traversal to store the tree—meaning nodes are listed layer by layer, left to right.

Here’s how to build the BST from this structure using a queue (perfect for level-order parsing):

Step 1: Define Your TreeNode Class #

First, create a node class to represent each question/answer:

class TreeNode:
    def __init__(self, data, is_question=True, parent=None):
        # Clean up the input text (strip ? and *)
        self.data = data.strip('? ') if is_question else data.strip('*? ')
        self.is_question = is_question
        self.parent = parent  # We'll use this for back navigation later
        self.left = None  # "Yes" branch
        self.right = None  # "No" branch

Step 2: Parse the File with Level-Order Logic #

Use a queue to process each node and attach its left/right children (yes/no branches):

def parse_tree_from_file(file_path):
    with open(file_path, 'r') as f:
        # Read all non-empty lines and strip whitespace
        lines = [line.strip() for line in f if line.strip()]
    
    if not lines:
        return None
    
    # Initialize root node
    root_line = lines[0]
    root = TreeNode(root_line, is_question=not root_line.startswith('*'))
    queue = [root]
    index = 1  # Track current position in the lines list
    
    while queue and index < len(lines):
        current_node = queue.pop(0)
        
        # Only question nodes have children
        if current_node.is_question:
            # Add left child ("Yes" branch)
            left_line = lines[index]
            index += 1
            left_node = TreeNode(left_line, is_question=not left_line.startswith('*'), parent=current_node)
            current_node.left = left_node
            # If it's a question, add to queue to process its children later
            if left_node.is_question:
                queue.append(left_node)
            
            # Add right child ("No" branch) if there are lines left
            if index < len(lines):
                right_line = lines[index]
                index += 1
                right_node = TreeNode(right_line, is_question=not right_line.startswith('*'), parent=current_node)
                current_node.right = right_node
                if right_node.is_question:
                    queue.append(right_node)
    
    return root

This will correctly map your text file into a valid BST, where each question node points to its yes/no branches.

2. Fixing Back Navigation (Returning to Previous Nodes) #

Recursion makes it hard to backtrack because Python manages the call stack automatically—you can’t easily "pop" back to a parent node without manual tracking. Here are two solid solutions:

Option 1: Use the Parent Pointer (Simplest) #

We added a parent attribute to the TreeNode class above. When you want to go back to the previous question, just set your current node to current_node.parent:

def play_game_with_parent(root):
    if not root:
        print("No game tree loaded!")
        return
    
    current_node = root
    while True:
        if current_node.is_question:
            print(f"\n{current_node.data}? (y/n/back)")
            answer = input().strip().lower()
            
            if answer == 'y':
                if current_node.left:
                    current_node = current_node.left
                else:
                    print("No more questions to ask!")
            elif answer == 'n':
                if current_node.right:
                    current_node = current_node.right
                else:
                    print("No more questions to ask!")
            elif answer == 'back':
                if current_node.parent:
                    current_node = current_node.parent
                    print("Returning to previous question...")
                else:
                    print("Can't go back further—you're at the start!")
            else:
                print("Please enter 'y', 'n', or 'back'.")
        else:
            print(f"\nIs it a {current_node.data}? (y/n/back)")
            answer = input().strip().lower()
            
            if answer == 'y':
                print("I got it right! 🎉")
                current_node = root  # Restart game
            elif answer == 'n':
                print("Oops, I missed it! We can add your answer later.")
                current_node = root  # Restart game
            elif answer == 'back':
                if current_node.parent:
                    current_node = current_node.parent
                    print("Returning to previous question...")
                else:
                    print("Can't go back further!")
            else:
                print("Please enter 'y', 'n', or 'back'.")

Option 2: Use an Explicit Stack (No Parent Pointer Needed) #

If you don’t want to add a parent attribute, track your path through the tree with a stack. Each time you move to a child, push it to the stack; when you want to backtrack, pop the stack to get the parent:

def play_game_with_stack(root):
    if not root:
        print("No game tree loaded!")
        return
    
    stack = [root]
    current_node = root
    
    while True:
        if current_node.is_question:
            print(f"\n{current_node.data}? (y/n/back)")
            answer = input().strip().lower()
            
            if answer == 'y':
                if current_node.left:
                    stack.append(current_node.left)
                    current_node = current_node.left
                else:
                    print("No more questions to ask!")
            elif answer == 'n':
                if current_node.right:
                    stack.append(current_node.right)
                    current_node = current_node.right
                else:
                    print("No more questions to ask!")
            elif answer == 'back':
                if len(stack) > 1:
                    stack.pop()
                    current_node = stack[-1]
                    print("Returning to previous question...")
                else:
                    print("Can't go back further—you're at the start!")
            else:
                print("Please enter 'y', 'n', or 'back'.")
        else:
            print(f"\nIs it a {current_node.data}? (y/n/back)")
            answer = input().strip().lower()
            
            if answer == 'y':
                print("I got it right! 🎉")
                stack = [root]
                current_node = root
            elif answer == 'n':
                print("Oops, I missed it! We can add your answer later.")
                stack = [root]
                current_node = root
            elif answer == 'back':
                if len(stack) > 1:
                    stack.pop()
                    current_node = stack[-1]
                    print("Returning to previous question...")
                else:
                    print("Can't go back further!")
            else:
                print("Please enter 'y', 'n', or 'back'.")

Both options work great—pick whichever fits your code style better.

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