如何在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 '())) 

它通過遞歸的每個級別維護父和子樹。