如何为通过eval输入的树将先序遍历改为层序遍历？

Got it, let's fix your code to do level-order traversal instead of the current pre-order one. The key difference here is that level-order traverses nodes level by level (root first, then all first-level children, then all second-level children, etc.), which requires a queue to keep track of nodes we need to process next.

The Problem with Your Current Code #

Your existing recursive function does pre-order traversal: it prints the current node first, then recursively processes each child. This dives deep into one branch before moving to the next, which isn't what we want for level-order.

The Solution: Use a Queue #

Here's how to rewrite it using a queue (we'll use collections.deque for efficient pops from the front):

from collections import deque

def level_order(node):
    if not node:
        return
    # Initialize queue with the root node
    queue = deque([node])
    while queue:
        # Get the first node in the queue
        current_label, current_children = queue.popleft()
        # Print the label (use end=' ' to keep everything on one line)
        print(current_label, end=' ')
        # Add all children to the end of the queue
        for child in current_children:
            if child:  # Handle empty child tuples just in case
                queue.append(child)
    # Optional: Print a newline at the end
    print()

tree = eval(input('Enter tree: '))
level_order(tree)

How It Works #

1. Queue Initialization: We start by adding the root node to the queue.
2. Processing Loop: While the queue isn't empty:
   • We take the first node from the front of the queue (this ensures we process nodes in the order they were added, i.e., level by level).
   • We print the node's label.
   • We add all of the node's children to the end of the queue, so they'll be processed after all nodes in the current level.
3. Edge Handling: The if child check ensures we don't add empty tuples (like ()) to the queue, though your input structure seems to only use empty tuples for leaf nodes' children, which won't cause issues anyway.

Testing with Your Example #

If you input:

("hello", (("a", ()), ("b", (("cde", ()), ("fg", ())))))

The output will be:

hello a b cde fg 

Which matches exactly what you need.

Optional: Collect Results Instead of Printing Directly #

If you prefer to collect the labels into a list first (maybe for further processing), you can modify the function like this:

from collections import deque

def level_order(node):
    if not node:
        return []
    queue = deque([node])
    result = []
    while queue:
        current_label, current_children = queue.popleft()
        result.append(current_label)
        for child in current_children:
            if child:
                queue.append(child)
    return result

tree = eval(input('Enter tree: '))
print(' '.join(level_order(tree)))

This will output the same string without the trailing space.

内容的提问来源于stack exchange，提问作者Z.Ken