hello,
I should check if all the leafs of a tree are on the same level...
Here an exemple for explain you my implementation. The tree :
(13)
(4 10) (30)
(3) (6 7) (11 12) (15 20) (35 40)
is implented thank to the list :
((13) ((4 10)((3))((6 7))((11 12))) ((30)((15 20))((35 40))))
(The leaf is consider too as a tree (without children))
My idea is to study each level. I explain with the example.
The top level contain only one node : (13). This node have got two children.
So I consider the second level, that contain two node : (4 10) and (30).
This two nodes have got children, so I continue.
So I consider the third level, that contain five "nodes" : (3), (6 7), (11
12), (15 20) and (35 40). All this nodes don't have got children, so all the
leaf are on the same level.
Does this method is the best?
If yes, can someone help me for the implementation in Lisp, because I have
got difficulties...
Thank.
Mathieu
P.S. I'm French so sorry for my English
--
=== Ma citation du mois ===
C'est l'incertitude qui nous charme. Tout devient merveilleux dans la brume.
Oscar Wilde - Extrait de "Le portrait de Dorian Gray"
"Mathieu" <·········@hotmail.com> wrote in message news:<············@wanadoo.fr>...
> ((13) ((4 10)((3))((6 7))((11 12))) ((30)((15 20))((35 40))))
Can someone give an example of where this kind of tree is useful?
I've reformatted it below to make it easier to read:
((13)
((4 10)
((3))
((6 7))
((11 12)))
((30)
((15 20))
((35 40))))
"Mathieu" <·········@hotmail.com> wrote in message
·················@wanadoo.fr...
> hello,
>
> My idea is to study each level. I explain with the example.
>
> The top level contain only one node : (13). This node have got two children.
> So I consider the second level, that contain two node : (4 10) and (30).
> This two nodes have got children, so I continue.
> So I consider the third level, that contain five "nodes" : (3), (6 7), (11
> 12), (15 20) and (35 40). All this nodes don't have got children, so all the
> leaf are on the same level.
>
> Does this method is the best?
> If yes, can someone help me for the implementation in Lisp, because I have
> got difficulties...
>
That seems like a workable approach. What have you tried so far? Show us the
code so we can give advice.
--
Coby
(remove #\space "coby . beck @ opentechgroup . com")
In article <············@wanadoo.fr>, Mathieu wrote:
> I should check if all the leafs of a tree are on the same level...
>
> Here an exemple for explain you my implementation. The tree :
>
> (13)
> (4 10) (30)
> (3) (6 7) (11 12) (15 20) (35 40)
>
> is implented thank to the list :
>
> ((13) ((4 10)((3))((6 7))((11 12))) ((30)((15 20))((35 40))))
>
> (The leaf is consider too as a tree (without children))
Were you told to encode your trees this way? If not, I'd rather
use something more clear, using `defstruct'. This encoding seems
pretty weird to me; whatever, you could start by writing little
functions that help you operate on your data, like a function
`get-children' that gets a node as input and outputs a list of
its children. Then, try to find a solution that uses /only/
these cute little interface functions and that works without any
knowledge whatsoever of the particular way you encode your trees.
Not only are you then free to change the data encoding without
breaking your solution, your solution will also be much easier to
understand (and to find!) as it it expressed solely in terms of
tree-operations instead of complicated `cadr's and `cddr's.
> My idea is to study each level. I explain with the example.
>
> The top level contain only one node : (13). This node have got two children.
> So I consider the second level, that contain two node : (4 10) and (30).
> This two nodes have got children, so I continue.
> So I consider the third level, that contain five "nodes" : (3), (6 7), (11
> 12), (15 20) and (35 40). All this nodes don't have got children, so all the
> leaf are on the same level.
>
> Does this method is the best?
I have no idea if it is the /best/ method, but it sounds fine and
clear to me :-)
> If yes, can someone help me for the implementation in Lisp, because I have
> got difficulties...
Start with those little interface functions. Come back if you still
have problems. Hope it helps.
Regards,
--
Nils Goesche
Ask not for whom the <CONTROL-G> tolls.
PGP key ID 0xC66D6E6F
Let's take just this much:
((13) ((4 10)((3))((6 7))))
Each (3) and (6 7) being in separate depth-signifying lists seems odd
given that they are sibling nodes. You would have to parse
(incompletely) as (node &rest wrapped-subnodes).
You could:
((13) (((4 10)((3)(6 7)))))
Then the signature is (node subnodes). or you could:
((13) ((4 10)(3)(6 7)))
and parse with (node &rest subnodes).
The one charm of your approach is that it is not positional: the top
node can be anywhere in the list encoding that tree. but then you cannot
parse at all using something like (note &rest...).
my two cents.
kenny
clinisys
Mathieu wrote:
>
> hello,
>
> I should check if all the leafs of a tree are on the same level...
>
> Here an exemple for explain you my implementation. The tree :
>
> (13)
> (4 10) (30)
> (3) (6 7) (11 12) (15 20) (35 40)
>
> is implented thank to the list :
>
> ((13) ((4 10)((3))((6 7))((11 12))) ((30)((15 20))((35 40))))
>
> (The leaf is consider too as a tree (without children))
>
> My idea is to study each level. I explain with the example.
>
> The top level contain only one node : (13). This node have got two children.
> So I consider the second level, that contain two node : (4 10) and (30).
> This two nodes have got children, so I continue.
> So I consider the third level, that contain five "nodes" : (3), (6 7), (11
> 12), (15 20) and (35 40). All this nodes don't have got children, so all the
> leaf are on the same level.
>
> Does this method is the best?
> If yes, can someone help me for the implementation in Lisp, because I have
> got difficulties...
>
> Thank.
> Mathieu
>
> P.S. I'm French so sorry for my English
>
> --
> === Ma citation du mois ===
> C'est l'incertitude qui nous charme. Tout devient merveilleux dans la brume.
>
> Oscar Wilde - Extrait de "Le portrait de Dorian Gray"