根据先序和中序输出结构构造完整的CommonLisp代码

tree-post.lisp

(defpackage :com.liutos.binary-tree
  (:use :cl))

(in-package :com.liutos.binary-tree)

(defclass tree-node ()
  ((value :initarg :value
          :accessor tree-node-value)
   (left :initarg :left
         :accessor tree-node-left)
   (right :initarg :right
          :accessor tree-node-right)))

(defun make-tree-node (value left right)
  (make-instance 'tree-node :value value :left left :right right))

(defun make-tree-by-pre-and-inorder-output/trivial (preorder-output inorder-output)
  "A trivial implementation of generating a binary tree from a preorder output and a inorder output. This function uses a lot of substring duplications for convenience."
  (check-type preorder-output string)
  (check-type inorder-output string)
  (format t "Processing ~A and ~A~%"
          preorder-output inorder-output)
  (cond ((equal "" preorder-output)
         nil)
        ((= 1 (length preorder-output))
         (make-tree-node (char preorder-output 0) nil nil))
        (t
         (let* ((root-value (char preorder-output 0))
                (pos (position root-value inorder-output)))
           (let ((left-pre (subseq preorder-output 1 (1+ pos)))
                 (left-in (subseq inorder-output 0 pos))
                 (right-pre (subseq preorder-output (1+ pos)))
                 (right-in (subseq inorder-output (1+ pos))))
             (make-tree-node root-value
                             (make-tree-by-pre-and-inorder-output/trivial
                              left-pre left-in)
                             (make-tree-by-pre-and-inorder-output/trivial
                              right-pre right-in)))))))

(defun postorder-print-tree (tree)
  "Output the information of the nodes in `tree' in the postorder."
  (when tree
    (postorder-print-tree (tree-node-left tree))
    (postorder-print-tree (tree-node-right tree))
    (princ (tree-node-value tree))))

;;; A non-trivial implementation
(defun make-tree-by-prein (preseq inseq)
  (labels ((aux (sp ep si ei)
             (cond ((> sp ep) nil)
                   ((= sp ep) (make-tree-node (char preseq sp) nil nil))
                   (t
                    (let* ((root-value (char preseq sp))
                           (offset (position root-value inseq :start si))
                           (left (aux (1+ sp) (+ sp offset)
                                      si (+ si offset -1)))
                           (right (aux (+ sp offset 1) ep
                                       (+ si offset 1) ei)))
                      (make-tree-node root-value left right))))))
    (aux 0 (1- (length preseq)) 0 (1- (length inseq)))))