这个二叉树中序遍历的实现可以改进吗？

Question

我为二叉树编写了一个简单的中序遍历函数 (toList1)。但是，我担心它的复杂性（内存/时间）。有没有更好的实现方式？

data Tree a = Empty | Node a (Tree a) (Tree a) 
toList1 :: (Tree a) -> [a]
toList1 Empty = []
toList1 (Node x lx rx) = (toList lx) ++ [x] ++ (toList rx)

Answer 1

Haskell 的附加 ++ 在其左参数的长度上线性执行，这意味着如果树 quadratic 性能=24=]向左倾斜。一种可能性是使用 difference list。

另一种方法是定义一个 Foldable 实例：

data Tree a = Empty | Node a (Tree a) (Tree a)

instance Foldable Tree where
    foldr f z Empty = z
    foldr f z (Node a l r) = foldr f (f a (foldr f z r)) l

那么，中序遍历自然就出来了：

toList :: Tree a -> [a]
toList = foldr (:) []

和

\> let tr = Node "root" (Node "left" Empty Empty) (Node "right" Empty Empty)
\> toList tr
["left","root","right"]

这个二叉树中序遍历的实现可以改进吗？

Can this implementation of in-order traversal of a binary tree be improved?

binary-tree

haskell

inorder