在有序二叉树遍历期间避免列表连接

Question

Haskell初学者看这里：二叉树的中序遍历很简单，例如：

data IntegerTree = Leaf Integer
                 | Node IntegerTree Integer IntegerTree

inorder :: IntegerTree -> [Integer]
inorder (Leaf n)     = [n]
inorder (Node l n r) = inorder l ++ [n] ++ inorder r

但是，在我看来，必须有更有效的实施方式。由于列表是单链接的，因此连接 inorder l 和 [n] 似乎很浪费，尤其是因为对一棵大树执行多次此操作。我可以通过不同方式编写相同的函数来避免这个问题吗？

我最初是在尝试解决以类似方式构造移动列表的汉诺塔拼图时想到这一点的，我希望可以使用类似的递归算法解决许多问题。

Answer 1

您可以传递一个额外的参数，即尾部：仍将生成该项目之后的项目列表。这看起来像：

inorder :: IntegerTree -> [Integer]
inorder = go <b>[]</b>
    where go <b>tl</b> (Leaf n) = n : <b>tl</b>
          go <b>tl</b> (Node l n r) = go (n : go <b>tl</b> r) l

因此，tl 是节点结束后将跟随的元素列表。在顶层，该列表为空（因此 go []）。当我们看到一片叶子时，我们发出包裹在 Leaf 中的项目 n，然后是尾巴。

对于Node，我们因此将对左元素执行递归，作为尾部n : go tl r，因此这是该节点的项目，然后是我们使用的右子树的递归给定的尾巴再次 tl。

Answer 2

嵌套 ++，因为您在顺序访问中使用的嵌套可能效率低下。这是因为list1 ++ list2会复制list1的（书脊），如下：

(1:2:3:[]) ++ list2
=
1: ((2:3:[]) ++ list2)
=
1:2: ((3:[]) ++ list2)
=
1:2:3: ([] ++ list2)
=
1:2:3:list2

复制第一个列表如果完成一次可能不会那么糟糕，但是当我们嵌套时 ++ 如

((list1 ++ list2) ++ list3) ++ list4

我们复制副本的副本，这会减慢一切，经常使 O(N^2) 的东西应该是 O(N)。

在计算list1 ++ list2时，一个关键的想法是：如果我们只在list1中保留一个指向末尾[]的“指针”，我们就可以避免复制，并简单地用指向 list2 的指针重写它，我们将获得恒定时间（破坏性）追加。

现在，我们在 Haskell 中有命令式可变性吗？不适用于常规列表。但是，我们可以将列表转换为“结束函数”，即不写

1:2:3:[]

对于列表，我们可以这样写

\end -> 1:2:3:end

表示相同的数据。列表的后一种表示称为“差异列表”。从常规列表转换为差异列表很简单：

type DList a = [a] -> [a]

toDList :: [a] -> DList a
toDlist = (++)

fromDlist :: DList a -> [a]
fromDlist dl = dl []

到目前为止还不错，但是如何连接两个 DList a？我们需要像

这样的东西

list1 = \end -> 1:2:3:end
list2 = \end -> 4:5:6:7:end

和return

concatenate list1 list2 = \end -> 1:2:3:4:5:6:7:end

原来concatenate就是简单的函数组合，(.)。 IE。 list1 . list2 正是我们需要的拼接。当我们评估

fromDList (list1 . list2)
-- i.e.
(list1 . list2) []

没有复制完成，因为 list1 的末尾立即链接到 list2。

因此，考虑到这一点，我们可以用最少的更改重写您的代码：

inorder :: IntegerTree -> [Integer]
inorder tree = fromDList (inorderDL tree)

inorderDL :: IntegerTree -> DList Integer
inorderDL (Leaf n)     = (n :)               -- that is, \end -> n: end
inorderDL (Node l n r) = inorderDL l . (n :) . inorderDL r

这将不会创建列表副本，因为在每个递归步骤生成每个子列表时，它的尾部不会是 []，而是指向下一个要连接的列表的“指针”。

最后，请注意，从不同的角度来看，这种方法正是 Willem 在他的回答中使用的方法。

在有序二叉树遍历期间避免列表连接

Avoid list concatenation during in-order binary tree traversal

binary-tree

haskell