從符號輸入構造樹

Question

我正在嘗試從字符串輸入中構造計劃語言的樹。以下是我已經嘗試 -

(define travsal (lambda (tree) 
      (cond 
       ((null? tree) '()) 
       (#t (append (travsal (car tree)) (cons (cadr tree) 
(travsal (caddr tree)))))))) 

(define tree1 '(((() 4()) 2 (() 5())) 1 ((() 6()) 3 (() 7())))) 

    (display tree1) 
    (newline) 

    (travsal tree1) 

正如你可以看到它只是迭代所提供的輸入，而不是做什麼實際的二叉樹應該做的。 對於如何使用節點和孩子從符號輸入保存樹來說，我感到非常震驚，例如 - （（（（）4（））2（（）5（）））1（（（）6（） ）3（（）7（）））））「然後打印出來就像上面的功能正在打印。

請幫忙，我在接受採訪時被問到這個問題，仍然無法解決它。

Answer 1

你是什麼意思「不做什麼實際的二叉樹應該做」？ 。遍歷代碼很好，它正在執行樹的in-order traversal。一些固定格式問題：

(define travsal 
    (lambda (tree) 
    (cond ((null? tree) '()) 
      (else (append (travsal (car tree)) 
         (cons (cadr tree) 
           (travsal (caddr tree)))))))) 

現在，請記住，你所提供的樹是二進制的，但不排序：

(define tree1 '(((() 4()) 2 (() 5())) 1 ((() 6()) 3 (() 7())))) 

如果我們畫它，它會是這樣的：

 1 
    / \ 
    2  3 
/\ / \ 
4  5 6  7 

其中，後中序遍歷將正確地得到該結果使用travsal過程時：

(travsal tree1) 
=> '(4 2 5 1 6 3 7)