遍历树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

回答

相关问题