Issues with variables and for loops

**Mr_Jack** · 01-09-2004

First, I know that my class code is not acceptable, but I don't want to mess with a bunch of functions to access the variables when I'm trying to figure out how to make binary trees for the first time. Then why not use a struct? Because I forgot how to do a ctor initializer and I need to have some default values for my variables. Next, here's my code:

Code:

#include <iostream>
using namespace std;

class node
{
public:
	node();
	int rowLen;
	node * levelLeft;
	node * levelRight;
	node * sibling;
	node * parent;
	node * childLeft;
	node * childRight;
	bool stem;
};
node::node()
{
	stem = 0;
	levelLeft = 0;
	levelRight = 0;
	sibling = 0;
	parent = 0;
	childLeft = 0;
	childRight = 0;
}

int main()
{
	int levels;
	
	cout << "How many levels should the tree have?" << endl;
	cin >> levels;

	node * stem = new node;
	stem->stem = true;
	node * levelHeads = stem;
	cout << levelHeads->stem << endl;
	node * current;
	float lastCount = .5;
	float currentCount;
	for(int a = 0; a < levels; a++)
	{
		current = levelHeads;
		currentCount = lastCount*2;
		for(float b = 0; b < (lastCount*2)-1; b++)
		{
			cout << current->stem << endl;
			current->rowLen = currentCount;
			current->levelRight = new node;
			current = current->levelRight;
		}
		lastCount = lastCount*2;
		levelHeads->childLeft = new node;
		levelHeads = levelHeads->childLeft;
	}
	/*
	node * topRow = stem;
	node * bottomRow = stem->childLeft;
	node * topCurrent = topRow;
	node * bottomCurrent = bottomRow;
	for(int a = 0; a < levels-2; a++)
	{
		for(int b = 0; b < topRow->rowLen; b++)
		{
			for(int c = 0; c < 2; c++)
			{
				bottomCurrent->parent = topRow;
				if(c == 0)
					topRow->childLeft = bottomRow;
				else
					topRow->childRight = bottomRow;
				bottomCurrent = bottomCurrent->levelRight;
			}
			topCurrent = topCurrent->levelRight;
		}
		topRow = bottomRow;
		bottomRow = bottomRow->childLeft;
	}*/
	return 0;
}

The problem is where the first set of loops is. When I set levelHeads to the address of stem, all goes as it should. But when I set current to the address of levelHeads (and stem), it doesn't appear to do anything when I print the value of current's stem member in the innermost for loop. The variable stem in levelHeads equals 1 and it apparently equals 0 in current. Please try to help me.

**Prelude** · 01-10-2004

>I don't want to mess with a bunch of functions to access the variables when I'm trying to figure out how to make binary trees for the first time.
Yet you want your tree to have left, right, sibling, parent, and left/right level pointers? A bunch of functions will not make your job harder if that's your goal.

It appears as if you want to build a perfect tree based on the height given. A full and perfect binary tree of height 4 has 15 nodes, 2^n - 1. However, you're going about it in the wrong way, really. Whether you like it or not, an insertion function is by far the easiest way to build a tree because you can use recursion to simplify things:

Code:

struct node {
  int data;
  node *left;
  node *right;
public:
  node ( int init, node *llink, node *rlink )
    : data ( init )
    , left ( llink )
    , right ( rlink )
  {}
};

node *insert ( node *root, int data )
{
  if ( root == 0 )
    root = new node ( data, 0, 0 );
  else if ( data < root->data )
    root->left = insert ( root->left, data );
  else
    root->right = insert ( root->right, data );

  return root;
}

Then to build a complete balanced tree, you find out how many nodes a tree of height n would have and build an array with that many items. You want an array so that each node can have a distinct value. That way you know that everything is working properly, instead of simply hoping as you look at a tree full of the same value.

The hardest part is actually building the tree. If you can binary search an array then you should have no difficulty. Play with this to get yourself started:

Code:

#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

struct node {
  int data;
  node *left;
  node *right;
public:
  node ( int init, node *llink, node *rlink )
    : data ( init )
    , left ( llink )
    , right ( rlink )
  {}
};

node *insert ( node *root, int data )
{
  if ( root == 0 )
    root = new node ( data, 0, 0 );
  else if ( data < root->data )
    root->left = insert ( root->left, data );
  else
    root->right = insert ( root->right, data );

  return root;
}

void build_tree ( node*& root, int *range, int left, int right )
{
  int mid = left + ( right - left ) / 2;

  if ( left > right )
    return;
  root = insert ( root, range[mid] );
  build_tree ( root, range, left, mid - 1 );
  build_tree ( root, range, mid + 1, right );
}

void print_node ( int value, int level )
{
  for ( int i = 0; i < level; i++ )
    printf ( "\t" );
  printf ( "%d\n", value );
}

void tree_structure ( node *node, int level )
{
  if ( node == NULL )
    print_node ( -1, level );
  else {
    tree_structure ( node->right, level + 1 );
    print_node ( node->data, level );
    tree_structure ( node->left, level + 1 );
  }
}

int main()
{
  int height;
  int nnodes;
  int *range = 0;
  node *root = 0;

  cout<<"Enter the height of the tree: ";
  if ( !( cin>> height ) ) {
    cerr<<"Sorry, invalid input\n";
    return EXIT_FAILURE;
  }
  nnodes = (int)pow ( 2, height ) - 1;
  range = new int[nnodes];
  for ( int i = 0; i < nnodes; i++ )
    range[i] = i;
  build_tree ( root, range, 0, nnodes - 1 );
  delete [] range;
  tree_structure ( root, 0 );
}

Since you are just starting with binary trees, I highly recommend you figure out the basics before adding additional links to the tree, they just make things more complicated. You can also see my tutorial in basic binary search trees in the FAQ.

Thread: Issues with variables and for loops

Thread Tools

Search Thread

Display

Issues with variables and for loops