在Lisp中通過BST搜索

Question

我正在編寫一個程序，指導機器人從BST到目標編號。該程序有兩個輸入參數，一個作爲整數的目標，以及一個表示機器人可以遵循的所有路徑的地圖。

即：（機器人64「（53（（）（64（）（））））））

凡64是目的地和53（（）（64（）（））））是BST。

我需要編寫該方法的幫助。這是我最初的工作。

(define (robot goal map) 
    (let ((x (car map))) 
    (define empty? '()) 
    (display x) 
    (cond (empty? x) 
      (robot goal (cadr map))) 
    (cond ((= goal x)) (display x)) 
    (cond (< x goal) 
      (robot goal (cadr map))) 
    (cond (> x goal) 
      (robot goal (caddr map))) 
    ;(display "NULL") 
) 
) 

它應該通過BST進行搜索，如果路徑中找到它打印（發現：＃T＃的...＃T＃），如果你的目標是樹而不是根（ ＃是一個位置編號，T是L或R，表示您在位置＃處左轉或右轉。

注意：我從來沒有在昨天使用過Lisp，所以很遺憾，如果我看起來有點丟失。

Answer 1

該過程的結構對於手頭的問題是不正確的 - 您沒有正確處理遞歸，並且您沒有爲此請求的輸出構建一個列表。使用cond的正確方法，並且您不應該重新定義現有程序map和empty?。另外，如果元素不在樹中，會發生什麼？除非確定該樹非空，否則不能執行(car tree)。

我將提供解決方案的正確結構並給出一些提示，以便您自己找出解決方案，如果在樹中未找到該元素，我們將返回一個列表，其中值爲not-found最後的位置。

(define (robot goal tree) 
    (cond ((empty? tree)  ; if the tree is empty 
     '(not-found))  ; return special value indicating it 
     ((= <???> goal) ; if the current element is goal 
     <???>)   ; return a list with current element 
     ((< goal <???>) ; if goal is less than current element 
     (cons <???>  ; cons current element 
       (cons <???> ; with L and advance the recursion 
        (robot goal <???>)))) ; going to the left 
     (else    ; otherwise 
     (cons <???>  ; cons current element 
       (cons <???> ; with R and advance the recursion 
        (robot goal <???>)))))) ; going to the right 

注意尋找一個BST正確的方式永遠是：

1. 檢查如果樹空
2. 如果沒有，檢查當前的元素就是我們正在尋找的一個爲
3. 如果沒有，檢查，如果我們要尋找的元素小於當前元素，並轉到左子樹，如果是這樣的話
4. 要不要去右子樹

作爲最後的意見，不要忘記測試您的解決方案：

(robot 64 '(53() (64()()))) 
=> '(53 R 64) 

(robot 42 '(53() (64()()))) 
=> '(53 L not-found)