0

这是一个计划程序，当一个人的名字和树作为输入时，查找二叉树的后代（树只有父亲和两个儿子 - bst）。我认为这里的主要问题是 getons 函数。我应该用什么替换这个功能？ 

(define (getfather FAMT)`
  (car FAMT)
   )


 (define (getson1 FAMT)
  (cadr FAMT)
 )

 (define (getson2 FAMT)
  (caddr FAMT)
 )

 (define (getsons FAMT)
 (cdr FAMT)
 )

 (define (empty? FAMT)
 (null? FAMT)
 )

(define (nosons? FAMT)
 (and (empty? (getson1 FAMT)) (empty? (getson2 FAMT)))
)

(define (getd FAMT)
 (cond ((empty? FAMT) '())
       ((nosons? FAMT) '())
       ((empty? (getson1 FAMT)) (getson2 FAMT))
       ((empty? (getson2 FAMT)) (getson1 FAMT))
       (else (getd (getsons FAMT))))
 )

(define (main1 person FAMT)
 (cond ((empty? FAMT) (getd '()))
       ((equal? person (getfather FAMT)) (getd FAMT))
       (else ( main1 person (getsons FAMT))))
 )



(define FAMT '(Pierce (Mark (Peter () ()) (Blaise () ())) (James () () )))

</code>
4

1 回答 1

0

getd和都是main1不正确的。在getd中，其中一个儿子失踪的情况必须递归调用getd另一个儿子，并且该else情况必须递归调用getd两个儿子并组合答案。无论如何，解决方案太复杂了，只需要两种情况，要么树是空的，要么是非空的，整个诀窍在于知道如何组合两个子树的答案，我选择附加元素来创建输出列表：

; returns a list of all descendants, including node at the root
(define (getd FAMT)
  (cond ((empty? FAMT)
         '())
        (else
         (append (list (getfather FAMT))
                 (getd (getson1 FAMT))
                 (getd (getson2 FAMT))))))

同样，main1一旦找到一个人，必须结合两个儿子的结果，并且它必须不断递归地查看树的两侧并结合它的答案，因为我们不知道搜索到的人在哪一侧（树不' t 似乎已排序）：

; finds a person and returns a list with all of
; its descendants, the list excludes the person
(define (main1 person FAMT)
  (cond ((empty? FAMT)
         '())
        ((eq? person (getfather FAMT))
         (append (getd (getson1 FAMT))
                 (getd (getson2 FAMT))))
        (else
         (append (main1 person (getson1 FAMT))
                 (main1 person (getson2 FAMT))))))

最后，您应该使用更大的树进行测试，问题中的示例树并未涵盖所有可能的情况，例如：

(define FAMT 
  '(Pierce
    (Mark 
     (Peter 
      (Logan () ()) 
      ()) 
     (Blaise 
      () 
      (Kurt () ())))
    (James 
     ()
     ())))

(main1 'Mark FAMT)
=> '(Peter Logan Blaise Kurt)
于 2013-10-29T14:41:27.697 回答