使用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))
Lisp实现二叉搜索树
使用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))
