查找二叉搜索树的高度

Question

我很难习惯Haskell中的递归,无论如何有人可以向我解释我将如何解决这个问题.我看过其他一些帖子,但我无法弄明白该怎么做.

我有我的类型

data BST = MakeNode BST String BST
             | Empty              

我不确定如何检查树下每一条路径的组合.

Answer 1

思考大多数递归函数的诀窍很简单:首先考虑基本情况,然后考虑递归情况.

基本情况通常是微不足道的 - 你什么时候知道树的高度而没有任何额外的计算？当然没有孩子的时候!所以基本情况是:

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)

我希望这澄清了设计递归函数的思维过程.