tree - lisp中的中序遍历

Question

我正在尝试在 Lisp 中按顺序遍历树。到目前为止，我设法构建了后序遍历，但顺序让我头疼..

树的格式是这样的:

 A
/ \
B  C          (A 2 B 0 C 2 D 0 E 0)
  / \
 D   E   

 (defun traverseTreeMain (l)
  (traverseTree l nil)
)

(defun traverseTree (l lc)
 (cond
  ((and (null l) (null lc)) nil)

  ((null l) (append nil (traverseTree lc nil)))

  ((=(cadr l) 0) (append   (list (car l))  (traverseTree (cddr l) lc)  ))

  ((= (cadr l) 1) (append nil  (traverseTree (cddr l)   
                                                        (append (   list (car l)   (- (cadr l) 1)   ) lc)
                                )   
                    )
    )

   (t (append nil (traverseTree (cddr l) (append lc (list (car l) (- (cadr     l)                                                   1))))))
)
)
;;run: (traverseTreeMain '(A 2 B 0 C 2 D 0 E 0))  --POSTORDER
;;=> (B D E C A)

Answer 1

通过调整此问题的解决方案可以找到另一种解决方案:Transforming trees in lisp ，其中需要将树从您的表示法转换为列表表示法 (node left-child right-child)。

解决方法如下:

(defun inorder(l)
  (if (null l)
      nil
      (inorder-sequence l)))

(defun inorder-sequence(l)
  (case (cadr l)
    (0 (values (list (car l)) (cddr l)))
    (1 (multiple-value-bind (left-subtree rest-of-list) (inorder-sequence (cddr l))
          (values (nconc left-subtree (list (car l))) rest-of-list)))
    (t (multiple-value-bind (left-subtree rest-of-list) (inorder-sequence (cddr l))
          (multiple-value-bind (right-subtree rest-of-rest) (inorder-sequence rest-of-list)
             (values (nconc left-subtree (list (car l)) right-subtree) rest-of-rest))))))

辅助函数 inorder-sequence 在每次调用时接收列表的其余部分，并返回几个值:

1. 包含与当前递归调用竞争的部分的顺序的列表，以及

2. 包含必须分析的其余元素的列表。

这样，在每个递归步骤中，函数本身可以使用第二个值来生成相对中序。

请注意，此方法适用于作为树节点的任何类型的元素，包括整数。