如何在方案中找到树的高度？

Question

定义一个Scheme程序（树高t），用于计算非空树的高度t

(define (height tree)
  (if (null? tree)
      0
      (max (height (caddr tree)))))

'(5(1(8)(2(1)(9)))(10)(4(9)))

应该返回4

Answer 1

你是对的，你忘记在答案中加1，但你也忘了拿cadr和caddr的最大值，你刚刚找到了caddr的最大值。您可以拥有一个树的左分支大于右分支，但您的程序将返回右分支的高度和不正确的答案。此代码应该可以解决您的问题。

(define (height tree)
  (if (null? tree)
        0
        (+ 1 (max (height (cadr tree)) 
                  (height (caddr tree))))))