调试二叉树生成器 LISP

Question

我试图编写一个程序来创建以列表作为输入的二叉树，但我运行遇到了一些错误。首先，如果我的元素少于 5 个，它根本不会输出任何内容，而当我的元素多于 5 个时，虽然我确实收到了我想要的输出，但它还会打印计算出的树的最后一侧。如果你们中的任何人可以帮助我调试它，将不胜感激！请在下面找到示例输入、示例输出以及我的代码。

 (make-cbtree '(8 3 10 1))
(8 (3 (1 () ()) ()) (10 () ())) 


(make-cbtree '(8 3 10 1 6))
(8 (3 (1 () ()) (6 () ())) (10 () ()))

;;This program will take a list and print a binary tree
(defun entry (tree) ;Node
    (car tree)
)


(defun left (tree) ;This function gets the left branch
    (cadr tree)
)


(defun right (tree) ;Function will get the right branch
    (caddr tree) 
)


(defun make-tree (entry left right) ;This function creates the node for a binary tree
    (if (= z y)
        (print(list entry left right))
    ) ;if z=y then prints the list
    (list entry left right)
)


(defun add (x tree) ;This function will add the element from list into tree
    (cond ((null tree) (make-tree x '() '())) ;Empty node, return nil
        ((= x (entry tree)) tree) ;if element from list equals node
        ;;if element from list is less than node then call make-tree function and add element to left side
        ((< x (entry tree)) (make-tree (entry tree) (add x(left tree)) (right tree)))
        ;;if element from list is greater than node then call make-tree function and add element to right side
        ((> x (entry tree)) (make-tree (entry tree) (left tree) (add x (right tree))))
    )
)


(defun make-cbtree(elements) ;Call this function to create a binary tree 
    (dolist (x elements) ;Using dolist to go through all elements in list
        (setf z (+ z 1))
        (setf tree (add x tree)) 
    ) 
    
)


;;Default values
(setf tree '())
(defvar z 0)
(defvar y 5)



(make-cbtree '(8 3 10 1))

Answer 1

首先，如果您要为二叉树定义抽象，定义抽象，而不是它的一部分。特别是你至少需要一个代表一棵空树的对象和一个空树的测试，这样你的代码就不会充满从抽象下面泄漏出来的晦涩的东西：

;;; A binary tree has an entry, a left and a right node
;;; The implementation is a three-element list

(defconstant empty-tree nil)

(defun empty-tree-p (tree)
  (eq tree empty-tree))

(defun entry (tree)
  (first tree))

(defun left (tree)
  (second tree))

(defun right (tree)
  (third tree))

(defun make-tree (entry left right)
  (list entry left right))

其次，我不知道模糊的全局变量是干什么用的——它们是一些遗留的调试工具吗？它们不需要存在并且肯定会破坏您的代码。我认为删除它们会使它起作用。

下面是一个有效的版本，不使用赋值，并且始终使用上面定义的抽象。

(defun add (x tree)
  ;; Add an entry to a tree
  (cond ((empty-tree-p tree)
         (make-tree x empty-tree empty-tree))
        ((= (entry tree) x)
         tree)
        ((< (entry tree) x)
         (make-tree (entry tree) (add x (left tree)) (right tree)))
        (t 
         (make-tree (entry tree) (left tree) (add x (right tree))))))

(defun add-elts-to-tree (elts tree)
  ;; Add a number of elements to a tree
  (if (null elts)
      tree
    (add-elts-to-tree (rest elts) (add (first elts) tree))))

(defun list->tree (l)
  (add-elts-to-tree l empty-tree))

现在，因为我已经为树定义了一个抽象，如果我愿意，我可以完全替换实现：

;;; A binary tree has an entry, a left and a right node
;;; The implementation is a function of one argument

(defconstant empty-tree (lambda (k)
                          (declare (ignore k))
                          nil))

(defun empty-tree-p (tree)
  (eq tree empty-tree))

(defun make-tree (entry left right)
  (lambda (k)
    (ecase k
      ((entry) entry)
      ((left) left)
      ((right) right))))

(defun entry (tree)
  (funcall tree 'entry))

(defun left (tree)
  (funcall tree 'left))

(defun right (tree)
  (funcall tree 'right))

调试二叉树生成器 LISP

Debugging Binary Tree Maker LISP

lisp

binary-tree

list

common-lisp