跳到主要内容

简述如何实现二叉树换行层序遍历 ?

参考答案:

二叉树的层序遍历通常使用队列(Queue)数据结构来实现,这种遍历方式会按照树的层次从上到下、从左到右遍历每个节点。然而,如果你希望实现换行层序遍历,即每一层的节点都打印在同一行,然后换行继续打印下一层的节点,你可以使用稍微修改过的层序遍历算法。

下面是一个简单的 Python 代码示例,演示如何实现二叉树的换行层序遍历:

from collections import deque

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

def print_level_order(root):
    if not root:
        return

    queue = deque([root])
    while queue:
        # 获取当前层的节点数
        level_size = len(queue)
        # 遍历当前层的所有节点
        for _ in range(level_size):
            node = queue.popleft()
            print(node.value, end=' ')
            # 将下一层的节点加入队列
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        # 当前层遍历完毕,换行
        print()

# 示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

print_level_order(root)

在这个示例中,我们首先检查根节点是否存在。然后,我们使用一个双端队列(deque)来存储待处理的节点。在每一轮循环中,我们首先获取当前层的节点数(即队列的长度),然后遍历这些节点。对于每个节点,我们打印其值,并将其左右子节点(如果存在)加入队列。当遍历完当前层的所有节点后,我们打印一个换行符,以便下一层的节点在新的一行上打印。