Haskell中由前序遍历序列生成二叉树函数返回空列表问题

问题原因 #

你的preOrderTree函数返回空列表的核心问题是遍历分割点i的范围错误：

• 当输入为[1]时，xs是空列表，length xs -1等于-1，此时[0..-1]是一个空列表，列表推导式没有任何元素可以遍历，最终返回空。
• 对于非空的xs，原代码的i只取到length xs -1，漏掉了i = length xs的情况——也就是左子树使用所有剩余元素、右子树为空的场景，这会导致很多合法的二叉树无法生成。

在二叉树前序遍历的规则里，根节点之后，左子树的前序序列长度可以是0到剩余元素的总长度（包含两端）：

• 左子树长度0 → 左子树为空，右子树使用所有剩余元素
• 左子树长度等于剩余元素长度 → 右子树为空，左子树使用所有剩余元素

修复后的代码 #

将i的范围修改为[0..length xs]即可覆盖所有合法的分割情况：

data BT a = Empty | Fork a (BT a) (BT a)
  deriving (Show)

treePreOrder :: BT a -> [a] 
treePreOrder Empty = [] 
treePreOrder (Fork x l r) = 
  [x] ++ treePreOrder l ++ treePreOrder r

preOrderTree :: [a] -> [BT a] 
preOrderTree [] = [Empty] 
preOrderTree (x:xs) = 
  [Fork x l r | i <- [0..length xs], let (ys, zs) = splitAt i xs, l <- preOrderTree ys, r <- preOrderTree zs]

测试验证 #

• 调用preOrderTree [1]会返回：

  [Fork 1 Empty Empty]
  

• 调用preOrderTree [1,2]会返回两种合法的二叉树：

  [Fork 1 (Fork 2 Empty Empty) Empty,Fork 1 Empty (Fork 2 Empty Empty)]
  

• 调用preOrderTree [1,2,3]会生成5种不同的二叉树（符合卡特兰数规律，n个节点的二叉树数量为第n个卡特兰数）。

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