Hello lads,

Let me start off by saying, no I'm not here to beg code off of you guys to do an assignment. I'm here to BUY code! JUST KIDDING

Anyway, this one is quite in depth...the object is to create a full binary tree of integers. The user is prompted for a height integer, and then the program is supposed to generate a full binary tree SUCH THAT doing a preorder traversal would output it in order (1 to whatever the final node is).

I've got most of the side things done, like computing the total number of nodes given the height, as well as a function to output the binary tree in order as specified...I just need to figure out an algorithm to put all the figures into the binary tree. For example, given 4, it would be something like this:
How am I going to do this? Any ideas? Does this look like a good idea?
Then I would have to have some sort of recursion, right, storing the values of level to ensure that the tree stayed only as deep as specified by the height value. Also, I could assumedly use a for loop since I know exactly how many values will be inserted, something like
Where insert() is going to somehow stick it into the tree!

I'm so muddled here. If anyone can put me on the path to clear thinking again, I'd much appreciate it. Gracias!

Hello neufunk. Welcome to GIDForums™.

I may be missing something here, so jump in and correct me when I go astray

Isn't a binary tree node defined by having the left child lower than the parent node and the right child higher than the parent node? Often times called a binary search tree?

So in your example, I would have expected something like:


If you have a "balanced" tree, seaching is unbelievably quick.

If this is not correct, what is your criteria for putting data in the tree?

I think you are on the right track though. I would use a structure very similar to what you have.

I think that the number of possible nodes in a tree is 2^level -1. So once the number of levels is input, you should be able to find the total number of nodes.

The "head" node will be ceiling(N/2).

As you go down left and right you will have to have to keep some kind of limits. The left node is average(head,lower limit), the right node is average(head,upper limit).

Well, normally, yes. The difference is between a binary tree and a binary search tree. A binary tree isn't necessarily ordered as such...when it becomes a binary SEARCH tree then it is. The requirements for my tree is that it is full (all possible nodes for its height) and that doing a preorder traversal will print out the nodes in order (1,2,3,4). So the program must stick the first node at the root, stick the second node in the left child, and continue to the left child until you hit the maximum height (that is why I thought a "level" variable was needed, to keep track of that). Then it starts to put things in the right node. Here is an example, using a height of 3:

1

1
/
2

1
/
2
/
3

1
/
2
/ \
3 4

1
/ \
2 5
/ \
3 4

1
/ \
2 5
/ \ /
3 4 6

1
/ \
2 5
/ \ / \
3 4 6 7

Make sense what I'm trying to do?

And thank you for the formula...its enraging that I didn't just look it up. My goodness, I spent hours trying to figure that out, and its just 2^height - 1? So simple...literally I scribbled all over pads of paper for an hour or two hoping to find that formula by looking at sample scenarios. The best I came up with was this code!

int i, totalnodes = 0, x = 1;
for (i=0; i<height; i++)
{
totalnodes = totalnodes + x;
x = x * 2;
}
cout<<endl<<"Total Nodes = "<<totalnodes<<endl;

What a convoluted way to get to the same answer!

Okay. Sorry 'bout that. So, if I understand the algorithm it is:

1. Goto the root and insert the first number
2. Go left & insert the next number until you hit the bottom.
3. Go to the parent node
4. Go right and insert the next number.
5. Repeat from 2 on.

The cool way to do this is recursion. You could probably also do something where the parent node is stored in your structure as well. (kind of a doubly linked tree )

I would imagine a recursive routine would work that would simply pass back the last number that was placed in the structure. This is off the top of my head, so it may be garbage...

That is assuming that you initialize your tree first. You know what size it needs to be, so that should be quite easy.


To use that you would need to initialize the root node and then pass it to the recursive structure.

Hope this helps. Like I say that is all untested, so you will need to make sure that it does what it is supposed to Good luck!

Thanks so much...I appreciate it. That made perfect sense, and it ended up compiling, though the insertnode() function gave a runtime error for some reason that I wasn't able to pin down. But fundamentally and in theory it did make perfect sense to me and helped me understand a reasonable way of solving the problem. You definately helped me prevent further head-against-the-wall bashing. :-)

Again, thanks...I had hit a brick wall and no amount of staring at the code would have gotten me any further! Merry Christmas and all that rot!