0

假设我有以下形式的自定义树数据类型：

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 tree@(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

我不确定这是否是按顺序横向的并且它不会返回正确的结果。

4

1 回答 1

2

我们希望在有序遍历中获得存储在二叉树中的第 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

这个想法是这样的：假设我们在 nodeA并且想要nth 值：

  A
 / \
B   C

如果B持有n-1值，则第nth 值是 的值A。如果B持有大于或等于n值，那么我们可以忽略树的其余部分并仅搜索B；所以我们只是递归到它。否则，我们应该寻找 中的值C，所以我们递归到它；在这种情况下，我们还需要更新n以反映 中存在一些值B，而 中存在 1 个值A。

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

于 2013-03-27T19:39:23.303 回答