Haskell中是否存在该广度优先二叉树反序列化函数的递归实现？

当然存在这样的递归实现，不需要依赖Seq或Vector，仅用Haskell的列表和递归就能完成，核心思路是按层递归处理节点，将序列化序列逐层分割为左、右子节点序列，再递归构建子树。

先明确序列化规则：层序遍历二叉树，用#（解析为Nothing）表示空节点Nil，序列按根→左子→右子→左子的左→左子的右→右子的左→右子的右的顺序排列。

完整实现代码 #

import Data.Maybe (maybeToList)

-- 二叉树定义
data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Show)

-- 广度优先反序列化函数，输入为解析后的 Maybe a 列表（# 对应 Nothing）
deserializeBFS :: [Maybe a] -> Tree a
deserializeBFS [] = Nil
deserializeBFS (m:ms) = constructTree [m] ms
  where
    -- 递归构建树：参数为当前层的节点Maybe列表、剩余序列化序列
    constructTree :: [Maybe a] -> [Maybe a] -> Tree a
    constructTree [] _ = Nil
    -- 当前层只有一个空节点，返回Nil
    constructTree [Nothing] _ = Nil
    -- 当前层是根节点，构建根及其左右子树
    constructTree [Just val] rest = Node val leftSub rightSub
      where
        (leftNodes, rightNodes, remaining) = splitChildren rest
        leftSub = constructTree leftNodes remaining
        rightSub = constructTree rightNodes remaining
    -- 当前层有多个节点，递归处理第一个节点，忽略空节点
    constructTree (m:ms) rest = case m of
      Nothing -> constructTree ms rest
      Just val -> Node val leftSub rightSub
        where
          (leftNodes, rightNodes, remaining) = splitChildren rest
          leftSub = constructTree leftNodes remaining
          rightSub = constructTree rightNodes remaining

    -- 将剩余序列分割为当前层所有节点的左子节点列表、右子节点列表，以及未处理的剩余序列
    splitChildren :: [Maybe a] -> ([Maybe a], [Maybe a], [Maybe a])
    splitChildren [] = ([], [], [])
    splitChildren xs =
      -- 下一层节点数量是当前层非空节点数的2倍
      let nonEmptyCount = length $ filter isJust xs
          (currentLevel, rest) = splitAt (2 * nonEmptyCount) xs
          -- 提取左子节点（偶数位置，从0开始）
          leftNodes = takeEvery 2 currentLevel
          -- 提取右子节点（奇数位置）
          rightNodes = takeEvery 2 $ drop 1 currentLevel
      in (leftNodes, rightNodes, rest)

    -- 每隔n个元素取一个
    takeEvery :: Int -> [b] -> [b]
    takeEvery _ [] = []
    takeEvery n (x:xs) = x : takeEvery n (drop (n-1) xs)

    -- 判断是否为非空节点
    isJust :: Maybe b -> Bool
    isJust (Just _) = True
    isJust Nothing = False

代码逻辑说明 #

1. 主函数deserializeBFS：接收解析后的Maybe a列表，调用辅助函数constructTree从根节点开始构建。
2. constructTree递归函数：
   • 若当前层无节点或只有空节点，返回Nil。
   • 若当前层是根节点，分割剩余序列得到左、右子节点列表，递归构建左、右子树。
   • 若当前层有多个节点，逐个处理非空节点，递归构建其子树。
3. splitChildren辅助函数：
   • 根据当前层非空节点数量，计算下一层节点总数（2倍非空节点数），从剩余序列中取出这部分节点。
   • 将下一层节点分割为左子节点列表（偶数位置）和右子节点列表（奇数位置），返回这两个列表和剩余未处理的序列。
4. takeEvery辅助函数：用于按间隔提取元素，分割左、右子节点序列。

示例验证 #

对于序列化序列解析后的[Just 2, Just 1, Just 3, Nothing, Just 0, Nothing, Nothing]，调用deserializeBFS会生成目标二叉树：

Node 2 (Node 1 Nil (Node 0 Nil Nil)) (Node 3 Nil Nil)

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