这种二叉树的顺序遍历的实现可以改进吗？ [英] Can this implementation of in-order traversal of a binary tree be improved?

问题描述

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

data Tree a = Empty |节点a（树a）（树a）
toList1 ::（树a） - > [a]
toList1 Empty = []
toList1（节点x lx rx）=（toList lx）++ [x] ++（toList rx）


解决方案

Haskell的追加 ++ 左边的参数，这意味着如果树向左倾斜，则可以获得二次性性能。
一种可能性是使用 差异列表 。

另一个是定义 <
$ b

 数据树a =空|节点a（树a）（树a）
 
实例可折叠树其中
 foldr fz Empty = z 
 foldr fz（Node alr）= foldr f（fa（foldr fzr） ）l 
  

然后，顺序遍历自然出现：

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

和

  \>让tr = Noderoot（NodeleftEmpty Empty）（NoderightEmpty Empty）
 \> toList tr 
 [left，root，right] 
  

I wrote a straightforward in-order-traversal function (toList1) for a binary tree. However, I worry about its complexity (memory / time). Is there a better way to implement it?

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)

解决方案

Haskell's append ++ performs linearly in the length of its left argument, which means that you may get quadratic performance if the tree leans left. One possibility would be to use difference list.

Another one would be to define a Foldable instance:

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

then, in-order-traversal comes out naturally:

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

and

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

这篇关于这种二叉树的顺序遍历的实现可以改进吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！