スキームツリーの深度

Question

ノードを受け取り、このノードをルートとするツリーの深さを返す関数を作成しようとしています。これまでのコードは次のとおりです。

(define (make-tree value left right) 
    (list value left right)) 

(define (value T) (car T)) 
(define (right T) (caddr T)) 
(define (left T) (cadr T)) 

(define (insert x T) 
    (cond ((null? T) (make-tree x '() '())) 
     ((eq? x (value T)) T) 
     ((< x (value T)) (make-tree (value T) 
            (insert x (left T)) 
            (right T))) 
     ((> x (value T)) (make-tree (value T) 
            (left T) 
            (insert x (right T)))))) 

どこから進んでいるのかよく分かりません。どんな助けもありがとう。

Answer 1

ツリーの深さは、次のように定義される。

1. 空のツリーは、非空のツリーは深さ1 +子供の深さ

の最大値を有する深さ0

を有しますコードでは、次のようになります。

(define (tree-depth tree) 
    (if (tree-empty? tree) 
     0 
     (+ 1 (max (tree-depth (tree-left tree)) 
       (tree-depth (tree-right tree))))))