遍歷樹LISP

-1

我想返回一個樹（不一定是二叉樹）的節點列表訪問inorder。例如：（a（b）（c（d）（e））），b - 左子樹，（c（d）（e）） - 右邊-subtree，一個 - 根。結果應該是：b，a，d，c，e遍歷樹LISP

這是我的代碼，但我總是看到「堆棧溢出」錯誤。有人可以幫幫我嗎？

;return left-subtree 
(defun left-tree(tree) 
    (cond 
    ((null tree) NIL) 
    ((not (listp tree)) NIL) 
    (t (car (cdr tree))) 
) 
) 

;return right-tree 
(defun right-tree(tree) 
    (cond 
    ((null tree) NIL) 
    ((not (listp tree)) NIL) 
    (t (cdr (cdr tree))) 
) 
) 

;perform inorder 
(defun inorder(tree) 
    (if (not (list-length tree)) 0 
    (append 
    (inorder (left-tree tree)) 
    (list (car tree)) 
    (inorder (right-tree tree)) 
) 
) 
)

來源

2015-12-08 DianaM

什麼是'（NOT（名單長樹））'的目的是什麼？「不」的數字總是假的。 –

樹遍歷的順序通常是前序（root，left，right）;後序（左，右，根）;並按順序（左，右，右）。我知道你張貼了一個輸出的例子，但當你有兩個以上的孩子時，「順序」意味着什麼？例如，如果你有樹（a（b）（c）（d）），那麼按順序遍歷應該是什麼？ a b a c a d？ –

另外一個問題是，當你想要一個扁平列表時，你在'inorder'的每個評估中創建一個新列表。 [Common Lisp：符號計算的簡潔介紹]（http://www.cs.cmu.edu/~dst/LispBook/）中有關'car/cdr遞歸'的部分可能對您有所幫助。 – Pascal

無限遞歸是由數字永遠不會是false-y的事實引起的。
用(null tree)代替(not (list-length tree))。
（也就是說，在遞歸結構，而不是在大小。）

一旦你解決這個問題，你會得到一個類型的錯誤是由於您的基本情況導致inorder - 它應該是nil，不0。

一旦你解決是，你會發現另一個問題：

CL-USER> (inorder '(a (b) (c (d) (e)))) 
(B A (C (D) (E)))

這遠遠正確的。

如果你看看right-tree的結果，它實際上不是你所聲稱的它應該是：

CL-USER> (right-tree '(a (b) (c (d) (e)))) 
((C (D) (E)))

正如你可以看到，這是在它的右子樹中一個元素的列表，而不是正確的子樹。
（測試單獨的每個功能是一個好主意，特別是如果你確定他們是正確的。）

根是第一個列表項目（car），左子樹是第二（中在cdr的car - cadr）和右子樹是第三項目（的cdr的cdr的car - caddr），而不是在開始第三項爲你寫的列表的其餘部分。
你需要提取的子樹：

(defun right-tree(tree) 
    (cond 
    ((null tree) NIL) 
    ((not (listp tree)) NIL) 
    (t (caddr tree)))) 

CL-USER> (inorder '(a (b) (c (d) (e)))) 
(B A D C E)

來源

2015-12-09 10:16:36 molbdnilo

回答

相關問題