list - 调试二叉树生成器 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))
 

标签： listlispbinary-treecommon-lisp

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))