Home > Archive > Prolog > March 2004 > Tree Height in Prolog
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Tree Height in Prolog
|
|
| Yupar Nyo 2004-03-27, 12:10 am |
| Hi,
How can I write a predicate for tree_height(Tree,Height) that binds Height
to the number of nodes on the longest path from the root to a leaf in a
binary tree. Trees are represented either "empty" or as "tree(L,Data,R)",
where L and R are the left and right are the left and right subtrees. Trees
must be instantiated at the time of the call.
Example:
:tree_height(tree(tree(empty,,a,empty),b
,tree(empty,c,tree(empty,d,empty))),
Z)
Z=3
It is quite complicated for me to solve. Any idea? Thanks.
Kind Regards,
Yupar
| |
| Matthew Huntbach 2004-03-27, 12:10 am |
| Yupar Nyo <yupar_nyo@bigpond.com> wrote:
> How can I write a predicate for tree_height(Tree,Height) that binds Height
> to the number of nodes on the longest path from the root to a leaf in a
> binary tree. Trees are represented either "empty" or as "tree(L,Data,R)",
> where L and R are the left and right are the left and right subtrees. Trees
> must be instantiated at the time of the call.
>
> Example:
>
> :tree_height(tree(tree(empty,,a,empty),b
,tree(empty,c,tree(empty,d,empty))),
> Z)
>
> Z=3
>
> It is quite complicated for me to solve. Any idea? Thanks.
If a tree is empty, the number of nodes on the longest path from the root to
to leaf is 0. That's obvious, isn't it?
Otherwise, the number of nodes on the longest path from the root to a leaf
is either 1+the number of nodes on the longest path from the root to leaf in
the left branch, or 1+the number of nodes on the longest path from the root
to the leaf in the right branch, depending on which is greater. Isn't that
also fairly obvious? So where's the problem?
Matthew Huntbach
| |
| Nick Wedd 2004-03-27, 12:10 am |
| In message <CPD4c.101828$Wa.40189@news-server.bigpond.net.au>, Yupar Nyo
<yupar_nyo@bigpond.com> writes
>Hi,
>How can I write a predicate for tree_height(Tree,Height) that binds Height
>to the number of nodes on the longest path from the root to a leaf in a
>binary tree. Trees are represented either "empty" or as "tree(L,Data,R)",
>where L and R are the left and right are the left and right subtrees. Trees
>must be instantiated at the time of the call.
>
>Example:
>
> :tree_height(tree(tree(empty,,a,empty),b
,tree(empty,c,tree(empty,d,empty))),
>Z)
>
>Z=3
>
>It is quite complicated for me to solve. Any idea? Thanks.
'empty' has depth 0. Other trees have a depth 1 greater than the depth
of their deeper subtree.
Nick
--
Nick Wedd nick@maproom.co.uk
|
|
|
|
|