如何用Python实现一般树的按高度（层序）遍历

Got it, let's walk through how to turn your idea into working code. What you're describing is level-order traversal (also called breadth-first traversal) for a general tree—visiting nodes layer by layer, starting with the root at index 0, then its direct children, then their children, and so on until we hit the bottom of the tree.

First, Define Your Tree Node Structure #

Before we write the traversal function, we need a way to represent a general tree node. Unlike binary trees, general trees can have any number of children, so we'll use a list to store child nodes:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []  # Holds all child nodes for this node

Implement the Traversal Function #

We'll use a queue to handle the level-by-level processing—queues are perfect for this because they follow a "first-in, first-out" order, ensuring we process all nodes in the current level before moving to the next. Here's how to expand your initial code framework:

def traversal(tree):
    # Handle empty tree case (matches your initial check)
    if not tree:
        print("No tree to traverse!")
        return []
    
    result = []
    # Initialize queue with the root node
    queue = [tree]
    
    while queue:
        # Dequeue the first node in the queue
        current_node = queue.pop(0)
        # Add the node's value to our result list
        result.append(current_node.value)
        # Enqueue all of the current node's children (in order)
        queue.extend(current_node.children)
    
    return result

Let's Test It with an Example #

Let's build a sample tree to verify the traversal works as expected:

# Build the tree
root = TreeNode("A")
b = TreeNode("B")
c = TreeNode("C")
d = TreeNode("D")
e = TreeNode("E")
f = TreeNode("F")

root.children = [b, c]
b.children = [d, e]
c.children = [f]

# Run the traversal
print(traversal(root))  # Output: ['A', 'B', 'C', 'D', 'E', 'F']

Key Notes About the Code #

• Queue Usage: We start with the root in the queue. For each node we process, we add all its children to the end of the queue—this ensures we finish processing the current level before moving to the next.
• General Tree Support: Unlike binary tree traversal, we don't have to check for left/right children—we just add all elements in the children list to the queue.
• Empty Tree Handling: We return an empty list along with your print statement, so you can still use the function's output even if the tree is empty.

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