SE250:lab-6:sdal039

First problem: tree height was returning values that were grossly larger than they should be. 990 versus 13 for 98 inserted nodes. Mark pointed out that i wasn't resetting the averageHeight variable after each loop iteration and so it simply kept adding up.

After running the experiment 3 times with sample sizes of 100, 10 and 1, inserting 98 nodes each time, this graph was produced: Average Height vs Number of Nodes

Code for generating data:

int numNodes, counter;
int limit = 99;
int sampleSize = 1;
int averageHeight = 0;

for ( numNodes = 0 ; numNodes < limit ; numNodes++ ) {
	printf(" %d\t", numNodes);
	counter = sampleSize;//preserve sample size during itteration
	while(counter-- > 0) {
	    averageHeight += height(makeRandomTree(numNodes)); //add heights
	}
	printf("%d\n", averageHeight / sampleSize);//take average
	averageHeight = 0;//reset average height	
}

Make Simple Tree made a new function called makeSimpleTree which makes a tree from 1,2,3,4,5,6,7 in order. makes testing of functions simpler as it is easy to determine what values should be returned. Especially helpful for testing search, when you have no idea what values are going to be in the tree when it is created due to the rand( ) function.

Node* makeSimpleTree( ) {
 Node* root = empty;

 insert( 4, &root );
 insert( 6, &root );
 insert( 5, &root );
 insert( 7, &root );
 insert( 2, &root );
 insert( 1, &root );
 insert( 3, &root );

 return root;
}

Minimum and Maximum Maximum and minimum were pretty straight forward

Node* minimum( Node* node ) {
   while (node->left != empty)
	node = node->left;
   return node;
}

Node* maximum( Node* node ) {
   while (node->right != empty)
	node = node->right;
   return node;
}

Lookup lookup not behaving quite right.. giving output

node key: 4, key: 5
node key: 6, key: 5
node key: 5, key: 5
Looking for: 5	Found: 4

so it is going through the tree, and at the point where node key == given key it ends, but returns 4 (the first node in the tree) for some reason

code for lookup:

Node* lookup( int key, Node* node ) {
   if ( node == empty)
	return node;//empty node

   if ( node->key <=  key ) {
	lookup(key, node->right);
   } else {
	lookup(key, node->left);  
   }

  if ( node->key == key ) {
      return node; //node has been found
   } 
}

Pre Order problems with next_pre.

Next_pre node: 2
Next_pre node: 1
Next_pre node: 2
Next_pre node: 1

It gets to the bottom, but can't get back up the tree.

After some playing around I managed to get it to print out all of the values in preorder, but not do it one node at a time.

Here is the code:

Node* next_pre( Node* node ) {
   if ( node != empty) {
	printf("%d, ", node->key);
	next_pre(node->left);
	next_pre(node->right);
   }
   return node;
}

This prints: 4, 2, 1, 3, 6, 5, 7

In Order

Node* next_pre( Node* node ) {
   if ( node != empty) {
	next_pre(node->left); 	
       printf("%d, ", node->key);
	next_pre(node->right);
   }
   return node;
}

This prints: 2, 1, 3, 4, 6, 5, 7

Post Order

Node* next_pre( Node* node ) {
   if ( node != empty) {
	next_pre(node->left); 	
       next_pre(node->right);
       printf("%d, ", node->key);
   }
   return node;
}

This prints: 2, 1, 3, 6, 5, 7, 4