Programming Forums > Application Development > C++

neufunk · Dec 2nd, 2004, 4:25 PM

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:

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!

Eggbert · Dec 4th, 2004, 9:18 AM

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

(Toggle Plain Text)

        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:

(Toggle Plain Text)

         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.

(Toggle Plain Text)

#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.

Dec 4th, 2004, 9:18 AM	#2
Eggbert Professional Programmer Join Date: Nov 2004 Posts: 250 Rep Power: 4	>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: (Toggle Plain Text) 1 2 9 3 6 10 13 4 5 7 8 11 12 14 15 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: (Toggle Plain Text) 8 4 12 2 6 10 14 1 3 5 7 9 11 13 15 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. (Toggle Plain Text) #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; } #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.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Dec 2nd, 2004, 4:25 PM	#1
neufunk Newbie Join Date: Dec 2004 Posts: 1 Rep Power: 0	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: 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!

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

Binary Trees