二叉树预序遍历

Question

我有一个二叉树的数据类型和一个计算其前序遍历的函数：

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-1], let (ys, zs) = splitAt i xs, l <- preOrderTree ys , r <- preOrderTree zs]

但它给出了一个空的树列表：

λ> preOrderTree [1,2,3]
[]
λ> preOrderTree [1]
[]

Answer 1

你很接近了。问题在于：

i <- [0..length xs-1]

您已排除

length xs

，但这是一个有效的拆分，它将把所有项目放入左分支中。

通过省略它，你就破坏了单例的功能。当您评价时：

preOrderTree[1]

你得到

length xs

的

-1

，所以

i <- [0..length xs-1]

不会生成树。结果，这个小错误导致整个递归没有生成树。

修正后：

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,3]
[Fork 1 Empty (Fork 2 Empty (Fork 3 Empty Empty)),Fork 1 Empty (Fork 2
(Fork 3 Empty Empty) Empty),Fork 1 (Fork 2 Empty Empty) (Fork 3 Empty
Empty),Fork 1 (Fork 2 Empty (Fork 3 Empty Empty)) Empty,Fork 1 (Fork 2
(Fork 3 Empty Empty) Empty) Empty]