检索二叉树的元素在Haskell

假设我有以下形式的自定义数据类型树：检索二叉树的元素在Haskell

data BalTree a = Leaf | Node Integer (BalTree a) a (BalTree a) deriving (Eq, Show, Read)

和创建大小为10的新的树，我会得到这样的：

Node 10 (Node 5 (Node 2 (Node 1 Leaf 'Z' Leaf) 'Z' Leaf) 
       'Z' 
       (Node 2 (Node 1 Leaf 'Z' Leaf) 'Z' Leaf)) 
'Z' 
     (Node 4 (Node 2 (Node 1 Leaf 'Z' Leaf) 'Z' Leaf) 
       'Z' 
       (Node 1 Leaf 'Z' Leaf))

如何在给定索引时检索按顺序横向的元素？

我尝试：

ind Leaf pos   = Nothing 
ind [email protected](Node n lt x rt) pos 
    | pos < 0   = Nothing 
    | pos > treeSize-1 = Nothing 
    | pos < hTreeSize = ind lt pos 
    | pos == hTreeSize = Just x 
    | pos > hTreeSize = ind rt (pos - hTreeSize) 
    where treeSize = size tree 
      hTreeSize = treeSize `div` 2

我不能完全肯定这是否是按顺序横向和它不会返回正确的结果。

来源

2013-03-27 rlhh

你的尝试有什么问题？ – dave4420 2013-03-27 19:29:38

btw，Haskell中的具体类型名称（与变量相对）必须大写。所以'BalTree'不是'balTree'。 – luqui 2013-03-27 19:53:37

Sorrry guys！我试图检索给定索引而不是第一个元素的元素。戴夫：我有一种感觉，我根本没有按顺序横穿，它没有返回正确的结果。 luqui：对不起，这是一个错字。 – rlhh 2013-03-27 19:58:50

我们想要按顺序步行得到存储在二叉树中的第n个值。我们知道存储在每个节点上的每棵树中存储的值的数量（Integer参数Node）。

data BalTree a = Leaf 
       | Node Integer (BalTree a) a (BalTree a) 

size :: BalTree a -> Integer 
size Leaf    = 0 
size (Node size _ _ _) = size 

nthInOrder :: BalTree a -> Integer -> Maybe a 
nthInOrder Leaf _ = 
    Nothing 
nthInOrder (Node _ left x right) n 
    | leftSize == n - 1 = Just x 
    | n <= leftSize  = nthInOrder left n 
    | otherwise   = nthInOrder right (n - leftSize - 1) 
    where 
    leftSize = size left

的想法是这样的：假设我们在节点A，并希望n个值：

A 
/\ 
B C

如果B持有n-1值，那么n个值是，A。如果B保存的值大于或等于n，那么我们可以忽略剩余的树并仅搜索B;所以我们只是回到它。否则，我们应该在C中寻找价值，所以我们会考虑它;在这种情况下，我们还需要更新n以反映B中有一些值，A中有一个值。

在最坏的情况下，这个算法走到了Leaf，所以复杂度是O(depth of tree)。如果树是平衡的，则复杂度为O(log2(size of tree))。

来源

2013-03-27 19:39:23 scvalex

Sooooo对不起。我试图在给定索引时检索一些随机元素。对不起，错字。 – rlhh 2013-03-27 19:57:24

检索二叉树的元素在Haskell

回答

相关问题