Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   Binary trees (http://www.velocityreviews.com/forums/t279839-binary-trees.html)

JC 12-08-2003 04:44 AM

Binary trees
 
Hi,

I'm looking for some help on Binary trees, in particular levels, heights
etc.

I need to find the levels of a tree, I also need to determine the minimum,
maximum and average leaf levels.

Any help would be greatly appreciated...
Thank you,
JC





Jack Klein 12-08-2003 05:38 AM

Re: Binary trees
 
On Sun, 7 Dec 2003 23:44:25 -0500, "JC" <keepit@secret.com> wrote in
comp.lang.c++:

> Hi,
>
> I'm looking for some help on Binary trees, in particular levels, heights
> etc.
>
> I need to find the levels of a tree, I also need to determine the minimum,
> maximum and average leaf levels.
>
> Any help would be greatly appreciated...
> Thank you,
> JC


Have you noticed that there is not a single mention of the C++
language in your post? You may be planning on implementing binary
trees in C++, but your question is about the data structures and
algorithms which are independent of programming language.

news:comp.programming is the best group for questions like this.

When you understand and have selected the data structures and
algorithm, if you have problems writing a correct C++ program to use
them, then post code here and ask for C++ language help.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

JC 12-09-2003 03:39 AM

Re: Binary trees
 
Sorry Jack,

But I fugure that it was understood what language I was using.
anyway...
I tried using a "inorder" function to get the levels.
in addition of using if statements to run trought the left and right side of
the tree.

The problem is when one side has multiple parents.

example
(35)
/ \
(27) (42)
/ \
(25) (31)
/ \
(29) (33)
/
(28)

so, if I have an if statement where

int level = 0;
p = root;
if ( p)
{
level++;
}
if ( (p->left == null) && (p->right == null) )
{
//end of branch
cout <<"\n Levels are <<level;
}

"Jack Klein" <jackklein@spamcop.net> wrote in message
news:ve38tvsfleobbtq620bi7a32t32j83jsgv@4ax.com...
> On Sun, 7 Dec 2003 23:44:25 -0500, "JC" <keepit@secret.com> wrote in
> comp.lang.c++:
>
> > Hi,
> >
> > I'm looking for some help on Binary trees, in particular levels, heights
> > etc.
> >
> > I need to find the levels of a tree, I also need to determine the

minimum,
> > maximum and average leaf levels.
> >
> > Any help would be greatly appreciated...
> > Thank you,
> > JC

>
> Have you noticed that there is not a single mention of the C++
> language in your post? You may be planning on implementing binary
> trees in C++, but your question is about the data structures and
> algorithms which are independent of programming language.
>
> news:comp.programming is the best group for questions like this.
>
> When you understand and have selected the data structures and
> algorithm, if you have problems writing a correct C++ program to use
> them, then post code here and ask for C++ language help.
>
> --
> Jack Klein
> Home: http://JK-Technology.Com
> FAQs for
> comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
> comp.lang.c++ http://www.parashift.com/c++-faq-lite/
> alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq




Karl Heinz Buchegger 12-09-2003 09:49 AM

Re: Binary trees
 
JC wrote:
>
> Sorry Jack,
>
> But I fugure that it was understood what language I was using.
> anyway...
> I tried using a "inorder" function to get the levels.
> in addition of using if statements to run trought the left and right side of
> the tree.
>
> The problem is when one side has multiple parents.


Your problem is still not a C++ problem but a problem in understanding
some algorithms.

>
> example
> (35)
> / \
> (27) (42)
> / \
> (25) (31)
> / \
> (29) (33)
> /
> (28)
>
> so, if I have an if statement where
>
> int level = 0;
> p = root;
> if ( p)
> {
> level++;
> }
> if ( (p->left == null) && (p->right == null) )
> {
> //end of branch
> cout <<"\n Levels are <<level;
> }


Since a binary tree is a recursive data structure, often recursive
functions are a natural choice:

int Height( tree* pNode )
{
if( pNode == NULL ) // an empty tree has height
// 0 by definition
return 0;

int HeightLeft = Height( pNode->left ); // determine height of left subtree
int HeightRight = Height( pNode->right ); // determine height of right subtree

// The height of this tree is then the maximum of the left and right
// subtree. Add one for this node.
//
//
// 27
// / \
// 1 +- 25 31 +--
// / 2
// 29 +--
//
// The height of the left subtree equals 1, the height of the right
// subtree equals 2. Thus the height of the total tree equals the
// maximum of both values: 2 plus 1 -> 3

return max( HeightLeft, HeightRight ) + 1;
}

--
Karl Heinz Buchegger
kbuchegg@gascad.at

Walter Kalata 12-10-2003 04:14 AM

Re: Binary trees
 
Obviously off-topic, but would anyone be able to supply any
algorithm-related newsgroups?

"Karl Heinz Buchegger" <kbuchegg@gascad.at> wrote in message
news:3FD59AC3.9E21DB92@gascad.at...
> JC wrote:
> >
> > Sorry Jack,
> >
> > But I fugure that it was understood what language I was using.
> > anyway...
> > I tried using a "inorder" function to get the levels.
> > in addition of using if statements to run trought the left and right

side of
> > the tree.
> >
> > The problem is when one side has multiple parents.

>
> Your problem is still not a C++ problem but a problem in understanding
> some algorithms.
>
> >
> > example
> > (35)
> > / \
> > (27) (42)
> > / \
> > (25) (31)
> > / \
> > (29) (33)
> > /
> > (28)
> >
> > so, if I have an if statement where
> >
> > int level = 0;
> > p = root;
> > if ( p)
> > {
> > level++;
> > }
> > if ( (p->left == null) && (p->right == null) )
> > {
> > //end of branch
> > cout <<"\n Levels are <<level;
> > }

>
> Since a binary tree is a recursive data structure, often recursive
> functions are a natural choice:
>
> int Height( tree* pNode )
> {
> if( pNode == NULL ) // an empty tree has height
> // 0 by definition
> return 0;
>
> int HeightLeft = Height( pNode->left ); // determine height of left

subtree
> int HeightRight = Height( pNode->right ); // determine height of right

subtree
>
> // The height of this tree is then the maximum of the left and right
> // subtree. Add one for this node.
> //
> //
> // 27
> // / \
> // 1 +- 25 31 +--
> // / 2
> // 29 +--
> //
> // The height of the left subtree equals 1, the height of the right
> // subtree equals 2. Thus the height of the total tree equals the
> // maximum of both values: 2 plus 1 -> 3
>
> return max( HeightLeft, HeightRight ) + 1;
> }
>
> --
> Karl Heinz Buchegger
> kbuchegg@gascad.at




JB 12-10-2003 02:14 PM

Re: Binary trees
 
I agree with Walter, although he hasn't stated anything <g>, are there any
Algorithm related Newsgroups, or are we just going to get flamed for trying
to ask questions and get a grasp on something. Alot of times I need to use
the language, C++, to help understand what is going on with the algorithm. .
..

Just a side note!

cheers,
JB

"Karl Heinz Buchegger" <kbuchegg@gascad.at> wrote in message
news:3FD59AC3.9E21DB92@gascad.at...
> JC wrote:
> >
> > Sorry Jack,
> >
> > But I fugure that it was understood what language I was using.
> > anyway...
> > I tried using a "inorder" function to get the levels.
> > in addition of using if statements to run trought the left and right

side of
> > the tree.
> >
> > The problem is when one side has multiple parents.

>
> Your problem is still not a C++ problem but a problem in understanding
> some algorithms.
>
> >
> > example
> > (35)
> > / \
> > (27) (42)
> > / \
> > (25) (31)
> > / \
> > (29) (33)
> > /
> > (28)
> >
> > so, if I have an if statement where
> >
> > int level = 0;
> > p = root;
> > if ( p)
> > {
> > level++;
> > }
> > if ( (p->left == null) && (p->right == null) )
> > {
> > //end of branch
> > cout <<"\n Levels are <<level;
> > }

>
> Since a binary tree is a recursive data structure, often recursive
> functions are a natural choice:
>
> int Height( tree* pNode )
> {
> if( pNode == NULL ) // an empty tree has height
> // 0 by definition
> return 0;
>
> int HeightLeft = Height( pNode->left ); // determine height of left

subtree
> int HeightRight = Height( pNode->right ); // determine height of right

subtree
>
> // The height of this tree is then the maximum of the left and right
> // subtree. Add one for this node.
> //
> //
> // 27
> // / \
> // 1 +- 25 31 +--
> // / 2
> // 29 +--
> //
> // The height of the left subtree equals 1, the height of the right
> // subtree equals 2. Thus the height of the total tree equals the
> // maximum of both values: 2 plus 1 -> 3
>
> return max( HeightLeft, HeightRight ) + 1;
> }
>
> --
> Karl Heinz Buchegger
> kbuchegg@gascad.at




osmium 12-10-2003 04:30 PM

Re: Binary trees
 
JB writes:

> I agree with Walter, although he hasn't stated anything <g>, are there any
> Algorithm related Newsgroups, or are we just going to get flamed for

trying
> to ask questions and get a grasp on something. Alot of times I need to

use
> the language, C++, to help understand what is going on with the algorithm.

..

Usenet is not a write only medium. You have to read what is written
including the links. Jack Klein answered that question *in this thread*!




All times are GMT. The time now is 03:52 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.