简述如何实现二叉树换行层序遍历 ?
参考答案:
二叉树的层序遍历通常使用队列(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)来存储待处理的节点。在每一轮循环中,我们首先获取当前层的节点数(即队列的长度),然后遍历这些节点。对于每个节点,我们打印其值,并将其左右子节点(如果存在)加入队列。当遍历完当前层的所有节点后,我们打印一个换行符,以便下一层的节点在新的一行上打印。