码农的博客

首先，我们要明确如何用LISP表示二叉树节点结构。一个节点由本身，左子树，右子树3部分组成。我们就可以用如下结构表示1个节点：

(node (left-subtree) (right-subtree))

比如，1个二叉树由3个节点组成，根为20， 左子树1个节点30， 右子树1个节点40。可以表示为：'(20 (30 () ()) (40 () ()))。

更复杂的情况，1个由7个节点组成的完全二叉树，从上到下从左到右，分别是1,2,3,4,5,6,7。则表示成 ‘(1 (2 (4 () ()) (5 () ())) (3 (6 () ()) (7 () ())))。

定义好二叉树的LISP表示方法后，就可以定义3种遍历算法了。

前序遍历：

(defun preorder(tree)
(if (or (null tree)
(not (listp tree))
(null (car tree))
(listp (car tree))
(not (= (length tree) 3))
(not (listp (car (cdr tree))))
(not (listp (car (cdr (cdr tree)))))
)
nil
(cons (car tree) (append (preorder (car (cdr tree))) (preorder (car (cdr (cdr tree))))))))

中序遍历：

(defun inorder(tree)
(if (or (null tree)
(not (listp tree))
(null (car tree))
(listp (car tree))
(not (= (length tree) 3))
(not (listp (car (cdr tree))))
(not (listp (car (cdr (cdr tree)))))
)
nil
(append (inorder (car (cdr tree))) (cons (car tree) '()) (inorder (car (cdr (cdr tree)))))))

后序遍历：

(defun postorder(tree)
(if (or (null tree)
(not (listp tree))
(null (car tree))
(listp (car tree))
(not (= (length tree) 3))
(not (listp (car (cdr tree))))
(not (listp (car (cdr (cdr tree)))))
)
nil
(append (postorder (car (cdr tree))) (postorder (car (cdr (cdr tree)))) (cons (car tree) '()))))