Page 1 of 1

Help for a tree manipulations.

Posted: Mon Nov 28, 2016 9:48 am
by matsui
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)
  (cond
   ((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")
nil
[183]> (french-string "b" "a")
t

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.

Re: Help for a tree manipulations.

Posted: Tue Nov 29, 2016 3:13 pm
by David Mullen
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.