如何实现二叉树的levelOrder遍历？已完成preOrder实现

你的先序遍历实现是正确的，完全符合先访问根节点、再递归左子树、最后递归右子树的逻辑。

层序遍历需要按节点深度升序，每层从左到右访问，核心思路是用队列维护待处理的节点层：

• 初始将根节点加入队列
• 每次处理当前队列的所有节点，收集它们的值
• 再把每个节点的非空左、右子节点加入下一层队列
• 重复过程直到队列为空

以下是完整实现代码：

data BTree a = Nil | Node a (BTree a) (BTree a) deriving Show

-- 你的先序遍历实现（保持不变）
preOrder :: BTree a -> [a]
preOrder Nil = []
preOrder (Node x lt rt) = x : preOrder lt ++ preOrder rt

-- 层序遍历实现
levelOrder :: BTree a -> [a]
levelOrder Nil = []
levelOrder root = levelOrderHelper [root]
  where
    -- 辅助函数：接收节点队列，返回层序遍历结果
    levelOrderHelper :: [BTree a] -> [a]
    levelOrderHelper [] = []
    levelOrderHelper nodes =
      -- 收集当前层所有节点的值
      [x | Node x _ _ <- nodes] ++
      -- 生成下一层节点队列：提取当前节点的非空左右子节点
      levelOrderHelper (concatMap (\node -> case node of
                                              Nil -> []
                                              Node _ lt rt -> [lt, rt]) nodes)

代码说明 #

1. levelOrderHelper 是递归核心：
   • 队列为空时返回空列表，标志遍历结束
   • 非空队列时，先通过列表推导式提取当前层所有节点的值（自动过滤Nil）
   • 用concatMap遍历当前节点，收集它们的左、右子节点作为下一层队列，递归处理下一层
2. 初始调用levelOrderHelper [root]，将根节点作为第一层队列

测试示例 #

构建一棵测试二叉树：

--    1
--   / \
--  2   3
-- / \
--4   5
testTree :: BTree Int
testTree = Node 1 (Node 2 (Node 4 Nil Nil) (Node 5 Nil Nil)) (Node 3 Nil Nil)

调用结果：

• preOrder testTree → [1,2,4,5,3]
• levelOrder testTree → [1,2,3,4,5]

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