SE250:lab-6:sbha077
Lab 6 Report
Task 1
Task 1 was about inserting values into a binary tree and getting the treeSize ( number of elements in the binary tree ) and the treeHeight ( height of the tree ).
The graph of the output is below.
<html><img src="http://img217.imageshack.us/img217/4210/binarytreezi6.jpg"/></html>
To get this output, the code was as follows:
int main ( void ) {
Node *binaryTree;
int treeSize;
int treeHeight;
for ( treeSize = 0; treeSize <= 500; treeSize++ ) {
binaryTree = makeRandomTree( treeSize );
treeHeight = height( binaryTree );
printf( "treeSize = %d\t\t treeHeight = %d\n", treeSize, treeHeight );
}
return 0;
}
From observation, the treeHeight starts leveling off at ~18 from treeSize ~350 onwards.
Task 2
For Task 2 we had to modify the " minimum " and " maximum " functions. The code is as follows:-
MINIMUM:
Node* minimum( Node* node ) {
if ( node == empty ) {
return empty;
}
while ( node->left != empty ) {
node = node->left;
}
return node;
}
MAXIMUM:
Node* maximum( Node* node ) {
if ( node == empty ) {
return empty;
}
while ( node->right != empty ) {
node = node->right;
}
return node;
}
To implement the two functions, the code is as follows:
int main ( void ) {
Node *binaryTree;
Node *min;
Node *max;
int minKey;
int maxKey;
binaryTree = makeRandomTree( 10 );
min = minimum( binaryTree );
max = maximum( binaryTree );
show_tree( 0, binaryTree );
printf(" minKey = %d\t maxKey = %d\n ", min->key, max->key );
return 0;
}
After testing this code a bit, I realised that I kept getting value of 41 at the parent node. So I realised that I had to seed the " makeRandomTree " function and modified it by doing the following:
Node* makeRandomTree( int size ) {
Node* root = empty;
srand( 100 ); // seed a random function , should be bundled with time to get a different value everytime.
while( size-- > 0 )
insert( rand( ), &root );
return root;
}
- The function does not seeded randomly everytime, that is one thing that I have yet to figure out.
Task 3
Task 3 was to modify the " lookup " function to find a particular key in the tree. Its not fully applicable because we have limited numbers in our tree. The functional code is as follows:
Node* lookup( int key, Node* node ) {
if ( node == empty ) {
return empty;
}
while ( key != node->key ) {
if ( key > node->key ) {
node = node->right;
} else {
node = node->left;
}
}
return node;
}
To implement this function, the following code was written:
int main ( void ) {
Node *binaryTree;
Node *min;
Node *max;
Node *find;
int minKey;
int maxKey;
binaryTree = makeRandomTree( 5 );
min = minimum( binaryTree );
max = maximum( binaryTree );
show_tree( 0, binaryTree );
printf( "minKey = %d\t maxKey = %d\n", min->key, max->key );
find = lookup ( 41, binaryTree );
if ( find->key == 41 ) {
printf( "\nFound the value!\n\n" );
}
return 0;
}
Task 4
Task 4 was about giving the value of the next and previous nodes in pre-order. The codes are as shown below:
PRE-ORDER NEXT
Node* next_pre( Node* node ) {
if ( node->left != empty ) {
return node->left;
} elseif {
return node->right;
} else {
if ( node->parent->right != empty ) {
return node->parent->right;
} else {
return empty;
}
}
}
PRE-ORDER PREVIOUS
Node* next_pre( Node* node ) {
if ( node->parent != empty ) {
return node->left;
} elseif ( node->right != empty ) {
return node->right;
} else {
if ( node->parent->right != empty ) {
return node->parent->right;
} else {
return empty;
}
}
}