Simple issue Trees in Lisp

[NickNatra]

Hello,
The subject says "simple", but is not really a piece of cake for me
Please help me( I started learning LISP 5 days ago ).

Code: Select all

   A
  / \
 B   C
    / \
   D   E

A tree can be represented in two ways
(A 2 B 0 C 2 D 0 E 0) (1)
(A (B) (C (D) (E))) (2)

->Convert a tree of type (2) to type (1).

This is my function:
____________________________________________________

Code: Select all

(defun  conv2to1(l)
	(cond
		((atom (car l)) (cons (car l) (length (cdr l))))
		(T  (append (conv2to1(car l)) (conv2to1 (cdr l))))
	)
) 

___________________________________________________
I'm not sure where I'm wrong, but i think I'm very close to the result

[NickNatra]

...A
../. \
.B ..C
..../ \
...D. E

The tree looks like this (corrected).
Hurry please

[ramarren]

Please use code tags in the future. There is a Code button above the editing are which can be used to display preformatted text like ascii-trees and code. I have also moved the topic to Common Lisp subforum, since I am assuming Common Lisp from the presence of DEFUN. If it is a different dialect of Lisp please specify.

Your function is not properly recursive, as the non-recursive case is not a base case. In this case a base case is an empty list representing lack of leaf nodes. Consider the non-base, recursive, case first. You need to collect a node value, a number of leaves, and then append to that a representation of leaves. A non-existent leaf does not appear in this representation, which means that the base case can return NIL, which in Common Lisp is equivalent to an empty list, which will be ignored when appending.

To generate leaf representation you need to call the function recursively on the second and third element of the list, which can be accessed with SECOND and THIRD functions, or the old fashioned CADR and CADDR, and then append the results.

[NickNatra]

Yes i'm using common lisp.
Tahks for the help.

Any tips here :

Code: Select all

(defun convert(l)
	(cond
		((null l) nil)
		((atom (car l)) (cons (car l) (length (cdr l))) )
		(T (cons (convert(cadr l)) (convert (caddr l))))
	)
)

English is not my native language so sorry my bad understanding

[ramarren]

You have to think what is being passed to the function. It is either a NIL, representing an non-existent leaf, or a list of one, two or three elements. This are the only two possibilities, which means that the conditional only needs two branches, not three as in your attempt.

A convenient fact about CADR and CADDR in this case is that since both CAR and CDR are defined to return NIL when called on NIL, they will return NIL even if the list is too short, which means you don't have to check length of the list when making the recursive call.

CONS constructs a list only if the second argument is a list or NIL (which is an empty list in CL), and it adds the first argument as an element, whatever the first argument is. To merge two lists you should use APPEND. In your case you want to add both the node and the number of leaves to the front of leaf representation, which means you have to use CONS nested.

[NickNatra]

i guess this is 90% correct

Code: Select all

(defun convert(l)
   (cond
		((null l) nil)
		(T (cons (car l)  (cons (cons(length(cdr l))(convert (cadr l)))(convert (caddr l)))))
   )
)

exept the fact that
for this

Code: Select all

> (convert '(A (B) (C (D) (E))))

the result is

Code: Select all

(A (2 B (0)) C (2 D (0)) E (0))

and not

Code: Select all

(A 2 B 0 C 2 D 0 E 0)

[ramarren]

The return value of your function is a list. You have two recursive calls, which means two lists. As I said, you need APPEND to append those two lists together. And then use CONS twice nested to add the number of leaves and the node to the result of that.

[NickNatra]

After a long struggle i got the expected result.

Code: Select all

(defun convert(l)
   (cond
		((null l) nil)
		(T (cons (car l)  (cons (length(cdr l)) (append (convert (cadr l))(convert (caddr l))))))
   )
)

Thank you for your time.
Your help means a lot to me .