企业官网建设流程全解析

使用sbcl实现二叉搜索树相关操作：

1. 定义节点

(defstruct node value left right)

2. 定义二叉树基础操作函数

(defun bst-copy (root) (if (null root) nil (let ((value (node-value root)) (left (node-left root)) (right (node-right root))) (make-node :value value :left (bst-copy left) :right (bst-copy right)) ) ) ) (defun bst-min (root) (if (null root) nil (let ((left (node-left root))) (if (not (null left)) (bst-min left) root ) ) ) ) (defun bst-merge (root) (if (null root) nil (let ((value (node-value root)) (left (node-left root)) (right (node-right root))) (cond ((null left) (bst-copy right)) ((null right) (bst-copy left)) (t (let ((r (bst-copy right))) (let ((min (bst-min r))) (setf (node-left r) (bst-copy left)) r ) )) ) ) ) ) (defun bst-insert (obj &optional root) (if (null root) (make-node :value obj) (let ((value (node-value root))) (cond ((= value obj) (make-node :value value :left (node-left root) :right (node-right root))) ((< value obj) (make-node :value value :left (node-left root) :right (bst-insert obj (node-right root)))) (t (make-node :value value :left (bst-insert obj (node-left root)) :right (node-right root))) ) ) ) ) (defun bst-remove (obj root) (if (null root) nil (let ((value (node-value root)) (left (node-left root)) (right (node-right root))) (cond ((= value obj) (bst-merge root)) ((< value obj) (make-node :value value :left left :right (bst-remove obj right))) (t (make-node :value value :left (bst-remove obj left) :right right)) ) ) ) ) (defun order (tree) (when tree (append (order (node-left tree)) (list (node-value tree)) (order (node-right tree)))))

其中，bst-copy用于复制二叉树，bst-merge用于合并子树，order用于中序遍历节点，bst-insert用于构造二叉树，bst-remove用于删除节点

3.测试

(defparameter bst nil) (setf bst (bst-insert 2 bst)) (setf bst (bst-insert 1 bst)) (setf bst (bst-insert 3 bst)) (setf bst (bst-insert 4 bst)) (setf bst (bst-insert 5 bst)) (defparameter bst1 (bst-insert 3 bst)) (format t "bst: ~a ~%~%" (order bst)) (format t "bst1: ~a ~%" bst1) (defparameter x (bst-copy bst)) (format t "~a ~%~%" (order x)) ;(trace bst-min) (format t "min: ~a ~%" (bst-min bst1)) (format t "merge: ~a ~%" (bst-merge bst1)) (setf bst (bst-remove 1 bst)) (format t "remove: ~a ~%" (order bst)) (setf bst (bst-remove 4 bst)) (format t "remove: ~a ~%" (order bst))