檢索二叉樹的元素在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

回答

相關問題