查找二叉查找樹的高度

我在使用Haskell遞歸方面遇到了問題，有人可以向我解釋我將如何去做這件事。我看了一堆其他職位，但我無法弄清楚如何去做。查找二叉查找樹的高度

我有我喜歡的類型爲

data BST = MakeNode BST String BST 
      | Empty

我不知道你怎麼我會考察下來的樹路徑的每一個組合。

來源

2012-03-08 user1204349

ohh，我忘了補充 – user1204349 2012-03-08 06:52:00

思考大多數遞歸函數的訣竅很簡單：首先考慮基本情況，然後考慮遞歸情況。

基本情況通常是微不足道的 - 你什麼時候知道樹的高度而不需要額外的計算？當然沒有孩子！所以基本情況是：

height Empty = 0

這很簡單。現在的下一個問題：二進制樹與孩子的高度是多少？

那麼，這也是簡單的 - 對於當前節點，加上最高子樹的高度，它是1。所以：

height MakeNode left _ right = 1 + max (height left) (height right)

（該_只是意味着我們不關心節點的字符串。）

因此，我們有一個很簡單的功能：

height :: BST -> Int 
height Empty    = 0 
height (BST left _ right) = 1 + max (height left) (height right)

我希望這闡明瞭設計遞歸函數的思想過程。

來源

2012-03-08 08:02:12

非常感謝回覆，現在我明白了邏輯，但是我得到一個錯誤。不能匹配預期類型'[A0]「與實際類型'BST」在長度的'的第一個參數「即'左」在'最大」，即'（長度左側）的第一個參數' '（+）'的第二個參數，即 'max（length left）（length right）' – user1204349 2012-03-08 08:09:48

@ user1204349您可能希望將'length'更改爲'height'。 – bereal 2012-03-08 08:12:47

謝謝，bereal。明顯的錯誤，應該是我自己找到的。 – user1204349 2012-03-08 08:14:04

該類型的任何樹都將具有無限高度，因爲無法表示葉子。

如果類型被定義爲：

data BST = MakeNode BST String BST 
     | MakeLeaf

然後樹葉的高度爲0，節點的高度爲1加上它的兩個子樹的最大高度。

來源

2012-03-08 06:50:04 pat

我忘了在沒有給出實際代碼的情況下添加空白部分 – user1204349 2012-03-08 06:53:29

+1 - 與往常一樣，我們熟練的問題是他甚至不能用英文制定樹的高度（或者至少他沒有告訴我們他可以），因此他的這種複雜的遞歸困難重重。我希望這裏有更多的人養成這樣的習慣：「只要你能用英語告訴我們，那麼我們就在哈斯克爾告訴你。」 – Ingo 2012-03-08 10:28:46

查找二叉查找樹的高度

回答

相關問題