Help for a tree manipulations.

You have problems, and we're glad to hear them. Explain the problem, what you have tried, and where you got stuck.
Feel free to share a little info on yourself and the course.
Forum rules
Please respect your teacher's guidelines. Homework is a learning tool. If we just post answers, we aren't actually helping. When you post questions, be sure to show what you have tried or what you don't understand.
Post Reply
Posts: 1
Joined: Mon Nov 28, 2016 8:46 am

Help for a tree manipulations.

Post by matsui » Mon Nov 28, 2016 9:48 am

Hello, first sorry about my English, I am French.
I am in computer science and I have a duty in Clisp.
This is an alphabetic sort, I block on a function.
The "ajoute" function, which adds a word to a tree, presents three cases:

The tree is empty: we create a tree with just the word as root: ( "word");
The word is greater than the root: we recurse with the right branch as root;
We recurse with the left branch as root.
Here are the correct tests :
(setq arbre (ajoute "k" nil)) => ("k")
(setq arbre (ajoute "a" arbre)) => ("k" ("a"))
(setq arbre (ajoute "m" arbre)) => ("k" ("a") ("m"))
(setq arbre (ajoute "n" arbre)) => ("k" ("a") ("m" nil ("n")))
(setq arbre (ajoute "b" arbre)) => ("k" ("a" nil ("b")) ("m" nil ("n")))

And here are my tests
(setq arbre (ajoute "k" nil)) => ("k")
(setq arbre (ajoute "a" arbre)) => ("k" ("a"))
(setq arbre (ajoute "m" arbre)) => ("k" ("a") ("m"))
(setq arbre (ajoute "n" arbre)) => ("k" ("a") ("m") ("m" ("n")))

Here is my function :

Code: Select all

(defun ajoute (mot arbre)
  (print arbre)
   ((atom arbre) (list mot . nil)) ; NOT LIST => ADDS AT TREE
   ((listp (car arbre)) (ajoute mot (car arbre)))
   ((equal (french-string mot (car arbre)) t) (append arbre (list (ajoute mot (cdr (cdr arbre)))))) ; RIGT TREE
   ((append arbre (list (ajoute mot  (car (cdr arbre)))))) ) )    ; LEFT TREE
french-string is a function that returns true if argument 1 is a word after argument 2 in alphabetical order.
exemple :
[182]> (french-string "a" "b")
[183]> (french-string "b" "a")

I think the problem with my function "adds" comes from my use of list and append, but I can not solve the problem. Do you have any leads to help me?
Thank you very much for your help and your time.

David Mullen
Posts: 78
Joined: Mon Dec 01, 2014 12:29 pm

Re: Help for a tree manipulations.

Post by David Mullen » Tue Nov 29, 2016 3:13 pm

I don't think I'd use append for this—it seems to call for something like this for the right-tree case:

Code: Select all

(list (car arbre) (cadr arbre) (ajoute mot (caddr arbre)))
And something similar for the left-tree case.

Post Reply