Common Lisp Binary Tree

Question

我想在Common Lisp中使用GNU ClISP編寫一個程序來編譯它。我想輸入一個列表，如(A(B (C)()) (D (E) (F (G)())))，並根據第一個單詞打印前，後或後序遍歷。示例：

(pre '(A(B (C)... etc)) 

我無法將我的邏輯轉換爲Clisp符號。我目前有以下代碼：

(defun leftchild (L)(cadr L)) 

(defun rightchild (L)(caddr L)) 

(defun data (L)(car L)) 

(defun pre (L)(if (null L) '()((data L)(pre(leftchild L))(pre(rightchild L))))) 

... similar in and post functions 

我收到編譯錯誤，說我應該在我的前函數中使用lambda。我認爲這是由於double（數據的前面，因爲它需要一個命令，但我不確定我應該放在那裏，我不認爲cond會起作用，因爲這會阻礙遞歸循環，將數據L打印，因爲它是現在編譯器不識別(print (data L))

我一直在這個代碼工作了一個多星期，試圖自己排除它，但我很茫然。如果有人可以解釋我做錯了什麼

另一個問題，我有我如何使程序提示行用戶輸入（前'（A ...等）），以便當我運行程序將運行的編譯文件而不是發出funcall錯誤？

謝謝你的時間。

Answer 1

簡答題：如果您想使用if，請注意您需要一個progn以便在後續和替代案例中擁有多個表單。

---

朗的答案 - 也解釋瞭如何遍歷積聚在列表被訪問節點：

我想這是家庭作業，所以我不會給你一個完整的解決方案，但你的問題表明你基本上有正確的想法，所以我會告訴你一個簡單，慣用的方式來做到這一點。

首先，你是對的：一個不帶引號形式的車應該是一個函數，所以基本上什麼樣(foo ...)，其中foo是不是一個函數（或宏，特殊形式......），整個事情是將被評估，將是一個錯誤。請注意，這不適用於特殊格式和宏（例如cond）。這些可以改變評估規則，而不是看起來像(foo bar)的所有內容都必須是通過正常評估規則進行評估的形式。最簡單的例子是quote，它簡單地返回它的參數未評估，所以(quote (foo bar))將而不是是一個錯誤。現在

，關於您的問題：

一個簡單的解決辦法是有一個累加器和遍歷樹，並在累加器推動值遞歸輔助函數。事情是這樣的：

(defun pre (node) 
    (let ((result (list))) 
    (labels ((rec (node) 
       (cond (... 
         ... 
         ...)))) 
     (rec node) 
     (nreverse result)))) 

的labels只是引入了一個本地助手功能，這將做實際的遞歸，外let給你一個蓄壓器，以收集節點值。此解決方案將以列表形式返回結果。如果您只是想打印每個節點的值，則不需要累加器或輔助函數。只需打印而不是推送，並使助手成爲頂層功能。

請記住，您需要遞歸停止的基本情況。你應該檢查在cond。然後，您需要每個子樹的遞歸步驟，並且您需要將節點的值推送到結果中。您執行這些步驟的順序決定了您是在執行事前，事中還是事後遍歷。你的代碼表明你已經理解了這個原則，所以你只需要使它在Lisp代碼中工作。您可以使用push將值推送到result和consp以檢查節點是否爲非空列表。由於空列表無關，因此基本上只需要在cond中進行一項測試，但您也可以像在代碼中一樣明確檢查節點是否爲null。