P69 - 二叉树的点串表示

Dotstring representation of binary trees
官方模块：Problems.P69　核心函数：treeToDotstring、dotstringToTree

编码规则

按前序遍历输出节点字符，空树输出 .。因为每个非空节点必有两个子树，这种编码不需要括号和分隔符也能唯一解析。

实现

方法一：递归下降

 1treeToDotstring :: Tree Char -> String
 2treeToDotstring Empty = "."
 3treeToDotstring (Branch x left right) =
 4  x : treeToDotstring left ++ treeToDotstring right
 5
 6dotstringToTree :: String -> Maybe (Tree Char)
 7dotstringToTree input = do
 8  (tree, rest) <- parseDotstring input
 9  if null rest then Just tree else Nothing
10
11parseDotstring :: String -> Maybe (Tree Char, String)
12parseDotstring [] = Nothing
13parseDotstring ('.':rest) = Just (Empty, rest)
14parseDotstring (x:rest) = do
15  (left, afterLeft)   <- parseDotstring rest
16  (right, afterRight) <- parseDotstring afterLeft
17  pure (Branch x left right, afterRight)

方法二：反向扫描栈

 1import Control.Monad (foldM)
 2
 3dotstringToTreeStack :: String -> Maybe (Tree Char)
 4dotstringToTreeStack input = do
 5  stack <- foldM step [] (reverse input)
 6  case stack of
 7    [tree] -> Just tree
 8    _      -> Nothing
 9  where
10    step stack '.' = Just (Empty : stack)
11    step (left:right:rest) value =
12      Just (Branch value left right : rest)
13    step _ _ = Nothing
14
15treeToDotstringDL :: Tree Char -> String
16treeToDotstringDL tree = build tree ""
17  where
18    build Empty = ('.' :)
19    build (Branch value left right) =
20      (value :) . build left . build right

把点串反向读取时，两个子树一定先于根出现。. 把空树压栈，普通字符弹出左右两棵子树并组成新树；最终栈必须恰好只剩一棵树。

方法对比

方法	解码状态	编码构造
递归下降	未消费字符串	`++` 拼接
反向扫描	显式树栈	差异列表

测试

 1>>> treeToDotstring tree1
 2"abd..e..c.fg..."
 3>>> dotstringToTree (treeToDotstring tree1) == Just tree1
 4True
 5>>> dotstringToTree "a."
 6Nothing
 7>>> dotstringToTreeStack (treeToDotstring tree1) == Just tree1
 8True
 9>>> treeToDotstringDL tree1 == treeToDotstring tree1
10True

编码长度恰为 $2n+1$ ： $n$ 个节点字符，加上 $n+1$ 个空子树标记。编码和解析都是 $O(n)$ 。

参考

← P68 遍历序列重建 | P70 多路树节点串 →