Number of levels in a tree

Discussion of Common Lisp

Number of levels in a tree

Postby Minato » Mon Nov 09, 2009 7:10 am

An n-ary tree is memorised in the following way:

(node (list-subtree-1) (list-subtree-2) ...)

As an example, the tree

A
/ \
B C
/ \
D E

is represented as follows:
(A (B) (C (D) (E)))

Return the number of levels of a tree

The problem is that I am only allowed to use the following functions: null, car, cdr, equal, atom, numberp, cons, cadr, caddr, cond and arithmtic functions.
Could anyone give me a function to return the levels of that kind of tree?
It would be great if you could give me a code that does not use the setq function.
Thanks in advance!
Minato
 
Posts: 8
Joined: Mon Nov 09, 2009 7:06 am

Re: Number of levels in a tree

Postby Harleqin » Mon Nov 09, 2009 9:51 am

Perhaps you'd like to look at these hints again. The problem isn't too hard.
"Just throw more hardware at it" is the root of all evil.
Svante
Harleqin
 
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Re: Number of levels in a tree

Postby Minato » Mon Nov 09, 2009 11:58 am

the problem is that i cannot use the setq function,and I can't figure out how to store the value of the deepest level found at a certain moment
Minato
 
Posts: 8
Joined: Mon Nov 09, 2009 7:06 am

Re: Number of levels in a tree

Postby methusala » Mon Nov 09, 2009 8:58 pm

If you know how to obtain a certain number using a certain form, why do you need to set a variable to it?

If needed, post whatever code you have so far and perhaps more hints will be forthcoming.
methusala
 
Posts: 35
Joined: Fri Oct 03, 2008 6:35 pm

Re: Number of levels in a tree

Postby Paul Donnelly » Mon Nov 09, 2009 11:12 pm

Minato wrote:the problem is that i cannot use the setq function,and I can't figure out how to store the value of the deepest level found at a certain moment

You don't need to store it. Either the right subtree of a node is deeper, or the left one is. So return the greater of the two.
Paul Donnelly
 
Posts: 148
Joined: Wed Jul 30, 2008 11:26 pm

Re: Number of levels in a tree

Postby Minato » Tue Nov 10, 2009 2:02 am

I did it,thanks for the hint Paul it helped a lot.And thanks to all of you too!
Minato
 
Posts: 8
Joined: Mon Nov 09, 2009 7:06 am

Re: Number of levels in a tree

Postby Harleqin » Tue Nov 10, 2009 5:05 am

Paul Donnelly wrote:
Minato wrote:the problem is that i cannot use the setq function,and I can't figure out how to store the value of the deepest level found at a certain moment

You don't need to store it. Either the right subtree of a node is deeper, or the left one is. So return the greater of the two.


And how do you do that for an "n-ary" tree? The answer includes a little bit of consing and recursion.
"Just throw more hardware at it" is the root of all evil.
Svante
Harleqin
 
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Re: Number of levels in a tree

Postby Minato » Tue Nov 10, 2009 8:29 am

I have other 2 examples for this problem and both werw bynary trees,so i did it for a bynary tree,I dont think it could be rezolved otherwise without usin set functions
Minato
 
Posts: 8
Joined: Mon Nov 09, 2009 7:06 am

Re: Number of levels in a tree

Postby methusala » Tue Nov 10, 2009 11:28 am

If your function is recursive, walking both the car and cdr parts of a list, and uses > to decide which depth number to return (such as to a + function), than it will work on n-ary trees. If you post the function you wrote, I'll post one I wrote and we can comment on it. Car is the first item in a list, Cdr is the rest of the list, so by walking down both car and cdr with a recursive function, your code will traverse a branch with any number of leaves or sub-branches. Car bites off the first element of successively smaller cdr lists, thus consuming a starting point list/tree of any length and any depth. The advantage of recursion is that by specifying how to handle any intermediate and final base cases in a given set of data, a function that calls itself doesn't have to use the additional complicated and data structure specific loops and variables that an imperative function would have to use. Specify the base cases, traverse both car and cdr, and trees of any n-ary complexity can be handled.
methusala
 
Posts: 35
Joined: Fri Oct 03, 2008 6:35 pm

Re: Number of levels in a tree

Postby Minato » Tue Nov 10, 2009 12:29 pm

this is my code:

(defun nivel (l k)
(cond
((null (cdr l)) k)
((> (nivel (cadr l) (+ k 1)) (nivel (caddr l) (+ k 1))) (nivel (cadr l) (+ k 1)))
(t (nivel (caddr l) (+ k 1) ) )
)
)
Minato
 
Posts: 8
Joined: Mon Nov 09, 2009 7:06 am

Next

Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 2 guests