J'ai essayé de créer un programme créant un arbre binaire avec une liste en entrée, mais je rencontre quelques erreurs. D'une part, si j'ai moins de 5 éléments, cela ne produit rien du tout, et lorsque j'ai plus de 5 éléments, alors que je reçois la sortie que je veux, il imprime également le côté final de l'arbre calculé. Si l'un d'entre vous pouvait m'aider à le déboguer, ce serait grandement apprécié ! Veuillez trouver ci-dessous, un exemple d'entrée, un exemple de sortie, ainsi que mon code.

 (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))
 
0
abdcg 13 nov. 2020 à 08:03

1 réponse

Meilleure réponse

Pour commencer, si vous allez définir une abstraction pour un arbre binaire, définissez l'abstraction, pas une partie de celui-ci. En particulier, vous voulez au moins un objet qui représente un arbre vide et un test pour qu'un arbre soit vide, donc votre code n'est pas plein de trucs obscurs qui ont fui sous l'abstraction :

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

Deuxièmement, je n'ai aucune idée à quoi servent les variables globales obscures - étaient-elles des restes de débogage ? Ils n'ont pas besoin d'exister et cassent certainement votre code. Les supprimer le fera fonctionner je pense.

Vous trouverez ci-dessous une version qui fonctionne, n'utilise pas d'affectation et utilise les abstractions définies ci-dessus tout au long.

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

Maintenant, parce que j'ai défini une abstraction pour les arbres, je peux, si je le souhaite, remplacer complètement l'implémentation :

;;; 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))
4
tfb 13 nov. 2020 à 18:46