Programming Forums - Binary Trees

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C++ (http://www.programmingforums.org/forum15.html)

- - Binary Trees (http://www.programmingforums.org/showthread.php?t=1387)

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 :P

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:

1
2 9
3 6 10 13
4 5 7 8 11 12 14 15

How am I going to do this? Any ideas? Does this look like a good idea?

struct node{
int value;
int level;
node* left;
node* right;
};

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

for (i=1;i<=totalnodes;i++)
insert(i);

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!

>doing a preorder traversal would output it in order
Preorder traversal or did you mean inorder traversal? Because most projects assume a binary search tree, and if a preorder traversal gave the values in order then it would violate the strict ordering of a binary search tree. As described, you want this tree:

        1

    2         9

  3    6    10     13

4  5  7  8 11  12  14  15

Whereas a proper binary search tree that's complete would be more like this:

         8

    4         12

  2    6    10     14

1  3  5  7  9  11  13  15

The latter is trivial to do, and I'll give you some quick code so that you can use it as an example for developing your own solution if it turns out that you really do want the fomer tree. :)

#include <stdio.h>

#include <stdlib.h>



struct node {

 int data;

 struct node *left, *right;

} *root = NULL;



struct node *insert ( struct node *root, int data )

{

 if ( root == NULL ) {

  root = malloc ( sizeof *root );

  if ( root == NULL ) {

   fprintf ( stderr, "Memory exhausted\n" );

   exit ( EXIT_FAILURE );

  }

  root->data = data;

  root->left = root->right = NULL;

 }

 else if ( data < root->data )

  root->left = insert ( root->left, data );

 else

  root->right = insert ( root->right, data );

 

 return root;

}



void traverse ( struct node *root )

{

 if ( root != NULL ) {

  traverse ( root->left );

  printf ( "%d ", root->data );

  traverse ( root->right );

 }

}



void build_complete ( int l, int r )

{

 if ( r >= l ) {

  int m = ( l + r ) / 2;

  root = insert ( root, m );

  build_complete ( l, m - 1 );

  build_complete ( m + 1, r );

 }

}



int main ( void )

{

 int n = ( 1U << 4 ) - 1;



 build_complete ( 1, n );

 traverse ( root );



 return 0;

}

As you can see, figuring out how many items are in a complete tree of level h is trivial. Simply take 2 to the power of h and subtract 1 from the result, this is the number of nodes you will need. Creating a proper binary search tree from there is simple with a divide and conquer technique.

Creating the type of tree that you want is not as obvious, but the solution will be similar in complexity. Keep that in mind when you try to work out your own implementation. :)