Mark: 6 revision(s)

2008-11-03T05:20:10Z

6 revision(s)

New page

== Q1 ==
Using the code

<Pre>int size_of_tree,i;
Node* node;

for( size_of_tree = 0; size_of_tree < i ; size_of_tree++) {
node = makeRandomTree(size_of_tree);
printf("height = %d for size = %d\n", height( node ), size_of_tree);
}
show_tree( 0, node );
</Pre>

Prints out a tree of 10nodes using random keys. Changing i will vary the size of the tree.

My results showed positive but not linear relationship between size and height of the tree. Maybe its exponential or logarithmic?

Ran out of time for the graph

== Q2 ==
Here are the functions for finding the minimum/maximum key values

Using a simple tree model the minimum key value should be located in the leftmost bottom corner
while the maximum should be in the rightmost bottom corner

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

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

I initially had some trouble working with the pointer input and struct types, but made it work with tutor help and trial/error
== Q3 ==
This function looks through the tree, branching left or right depending on the key value of the current node with the key we are looking for.

<Pre>Node* lookup( int key, Node* node ) {
while( key != node->key ){

if( key == node->key ){
return node;
} else

if( ( node != empty ) && ( key < node->key ) ){
node = node->left;
} else {
node = node->right;
}
return empty;
}
}</Pre>

This will return an empty node if the key isnt found.

At first I thought this method would not work and we had to use recursion to look through every single value in the tree, then someone pointed out that each node acted as a "sorter" for the next key; if the key was smaller it would be to the left of the current node, if bigger then it would be located to the right.

== Q4 ==
Had a lot of trouble getting started with this question. First I thought we had to list the remaining sequence in Preorder, but I forgot how to implement recursion.

After drawing a simple tree diagram by hand I managed to create a sequence of conditionals to check for the next value in Preorder

<Pre>Node* next_pre( Node* node ) {
if( node->parent == empty ){

if ( node->left == empty ){
return node->right;
} else {
return node->left;
}

} else

if( node->parent->right == empty ){
return node->parent;
} else {
return node->parent->right;
}
return empty;
}</Pre>

== Q5 ==

report to follow

SE250:lab-6:tlou006 - Revision history

Mark: 6 revision(s)