Lisp中的有序遍历 [英] Inorder traversal in lisp

问题描述

我正在尝试遍历Lisp中的树顺序.到目前为止，我设法建立了Postorder遍历，但是顺序使我头疼.

I am trying to iterate through a tree inorder in Lisp. So far, I managed building the Postorder traversal but inorder gives me headaches..

树的格式是这样:

 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)

推荐答案

可以通过将解决方案适应以下问题来找到另一种解决方案:用Lisp转换树，需要将树从您的表示法转换为列表表示法(node left-child right-child).

Another solution can be found by adapting the solution to this question: Transforming trees in lisp, where it is required to transform a tree from your notation to the list notation (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接收列表的其余部分，并返回几个值:

The auxiliary function inorder-sequence at each call receives the rest of the list, and returns a couple of values:

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

1. the list containing the inorder of the part competing to the current recursive call, and

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

a list containing the rest of the elements that must be analyzed.

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

In this way, at each recursive step, the function itself can use the second value to generate the relative inorder.

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

Note that this approach works for any kind of elements as nodes of the tree, including integers.

这篇关于Lisp中的有序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！