Mark: 18 revision(s)

2008-11-03T05:20:09Z

18 revision(s)

New page

= '''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;
}
}
}

== '''Task 5''' ==

== '''Task 6''' ==

SE250:lab-6:sbha077 - Revision history

Mark: 18 revision(s)