Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Binary trees

Reply
Thread Tools

Binary trees

 
 
JC
Guest
Posts: n/a
 
      12-08-2003
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




 
Reply With Quote
 
 
 
 
Jack Klein
Guest
Posts: n/a
 
      12-08-2003
On Sun, 7 Dec 2003 23:44:25 -0500, "JC" <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
JC
Guest
Posts: n/a
 
      12-09-2003
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)
/
(2

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" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On Sun, 7 Dec 2003 23:44:25 -0500, "JC" <(E-Mail Removed)> 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



 
Reply With Quote
 
Karl Heinz Buchegger
Guest
Posts: n/a
 
      12-09-2003
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)
> /
> (2
>
> 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
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
Walter Kalata
Guest
Posts: n/a
 
      12-10-2003
Obviously off-topic, but would anyone be able to supply any
algorithm-related newsgroups?

"Karl Heinz Buchegger" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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)
> > /
> > (2
> >
> > 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
> (E-Mail Removed)



 
Reply With Quote
 
JB
Guest
Posts: n/a
 
      12-10-2003
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" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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)
> > /
> > (2
> >
> > 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
> (E-Mail Removed)



 
Reply With Quote
 
osmium
Guest
Posts: n/a
 
      12-10-2003
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*!


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Binary search trees (AVL trees) jacob navia C Programming 34 01-08-2010 07:27 PM
Lock-free binary trees Joe Seigh Java 27 07-16-2006 08:54 PM
Binary Trees jova Java 11 04-26-2004 06:41 AM
Binary Trees jova C++ 11 04-26-2004 06:41 AM
Non-Binary Trees Will Oram C++ 3 10-28-2003 01:01 PM



Advertisments