SE250:lab-6:jhor053
Lab 6
Task 1
My code:
int main (void){
Node *first;
int i = 0;
//Node test;
for(i = 0; i < 50; i++){
first = makeRandomTree(i);
//show_tree(0, first);
//printf("\n");
printf("%d, %d\n", i, height(first) );
}
}
My graph:
<html><img src="http://www.gotmilk.co.nz/~gm_modnar/250labs/lab6/task1-01.jpg" border="0" /></html>
My relationship: I think that it is relatively directly proportional but overall it is pretty random on either side of the line of best fit.
Task 2
My code:
Node* minimum( Node* node ) {
if( node->left != empty)
return minimum(node->left);
return node;
}
Node* maximum( Node* node ) {
if( node->right != empty)
return maximum(node->right);
return node;
}
int main (void){
Node* first;
Node *min;
Node *max;
int i = 0;
int minint, maxint;
for(i = 1; i < 5; i++){
first = makeRandomTree(i);
show_tree(0, first);
min = minimum(first);
max = maximum(first);
minint = min->key;
maxint = max->key;
printf("The min is: %d\n", minint );
printf("The max is: %d\n", maxint );
printf("\n");
}
}
My print out:
41 [0]
The min is: 41
The max is: 41
6334 [1]
18467 [0]
The min is: 6334
The max is: 18467
15724 [2]
19169 [1]
26500 [0]
The min is: 15724
The max is: 26500
11478 [0]
24464 [3]
26962 [2]
29358 [1]
The min is: 11478
The max is: 29358
Overall: This wasn't too bad is if the tree is implemented according to the defining principles it will work no problem.
Task 3
My code:
Node* lookup( int key, Node* node ) {
if(node == empty){
return empty;
}else if(key == node->key){
return node;
}else if(key < node->key){
return lookup(key, node->left);
}else{
return lookup(key, node->right);
}
}
int main (void){
Node* first;
Node *keyloc;
int i = 0;
int lookupres, key;
for(i = 1; i < 5; i++){
first = makeRandomTree(i);
show_tree(0, first);
printf("Please enter key to find: \n");
scanf("%d", &key);
keyloc = lookup(key, first);
if(keyloc == empty){
lookupres = 0;
}else{
lookupres = keyloc->key;
}
printf("The key is: %d\n", key );
printf("The FOUND key is: %d\n", lookupres );
printf("\n");
}
}
my output:
41 [0]
Please enter key to find:
5
The key is: 5
The FOUND key is: 0
6334 [1]
18467 [0]
Please enter key to find:
6334
The key is: 6334
The FOUND key is: 6334
15724 [2]
19169 [1]
26500 [0]
Please enter key to find:
26500
The key is: 26500
The FOUND key is: 26500
11478 [0]
24464 [3]
26962 [2]
29358 [1]
Please enter key to find:
26962
The key is: 26962
The FOUND key is: 26962
Explanation:
It gets teh user input of what key to find after printing out the tree so as to be able to tell whether or not it exists in teh tree. Also prints out 0 for FOUND key if not found.
It works first by checking whether it is an empty node and returns such if so. Next is if the key is equal to the current node and if so returns current node (ie found the key). Next it sees the key is smaller than the current node and if so will venture only off to the left as per the defining properties, the same applies to the next statement but as per going to teh right tree.
Alternative way: