Haskell:深度优先搜索有序树

Question

首先，我有一个有序树的数据类型：

data OrdTree a = OrdTree a [OrdTree a]
                    deriving (Show)

我需要按照 DFS（深度优先搜索）的顺序获取所有节点的列表。

这是我解决这个问题的尝试：

dfsTreeList :: OrdTree a ->  [a]                       
dfsTreeList (OrdTree a (x:xt)) = a : (dfsTreeList x) ++ (dfsTreeList (OrdTree a xt))                          
dfsTreeList (OrdTree a []) = a : []

但是出现了一个新问题：每个非最后节点都被包含在列表中两次。

例如输入数据：

dfsTreeList (OrdTree 7 [(OrdTree 3 [(OrdTree 1 []), (OrdTree 4 [])]), (OrdTree 10 [(OrdTree 8 []), (OrdTree 12 [])])])

结果：

[7,3,1,3,4,3,7,10,8,10,12,10,7]

有人有什么想法吗？感谢您的回复。

Answer 1

这里

dfsTreeList (OrdTree a (x:xt)) = a : (dfsTreeList x) ++ (dfsTreeList (OrdTree a xt))

您正在复制 a。您可以尝试将函数应用于列表中的每个子树，例如

dfsTreeList (OrdTree a xs) = a : concat (map dfsTreeList xs)

您也可以使用 concatMap 或 >>= 达到相同的效果。

Haskell:深度优先搜索有序树

Haskell: depth-first search for ordered tree

tree

haskell

depth-first-search