如何在Tree中找到前辈

Question

能否请你帮我一个函数，我需要在树中找到前辈，但是它会返回一个空列表，如何在不使用“set！”的情况下返回前辈。

(define (predecessor val tree) 
    (cond ((null? tree) (node tree)) ; If the set is null result is predecessor   
     ((> val (node tree)) (predecessor val (right-branch tree))); if val is greater 
     ((< val (node tree)) (predecessor val (left-branch tree))))) ; if val is lesser 

(define (node tree) 
    (car tree)) 

(define (left-branch tree) 
    (cadr tree)) 

(define (right-branch tree) 
    (caddr tree))) 

Answer 1

由于递归过程的基本情况，它返回空列表。 它退出的唯一时间是(null? tree)为真，tree是您在那里返回的。

这是怎么回事（未经测试）？

(define (predecessor tree val) 
    (define (helper sub-tree parent) 
    (cond (((= (node sub-tree) val) parent) 
      ((< (node sub-tree) val) (helper (right-branch sub-tree) sub-tree)) 
      (else (helper (left-branch sub-tree) sub-tree))))) 
    (helper tree '())) 

它通过递归的每个级别维护父和子树。