SE250:lab-6:jpar277
Overview
It took a while to read the code and understand what was going on. But once I understood the functions and what they were doing, I think this was a reasonably simple lab. It was a little time consuming looking up things here n there to help with the tasks and that resulted in me not completing the lab. Perhaps I will finish it some other time.
Task1
<html><img src="http://img375.imageshack.us/img375/5721/graphbm5.jpg" border="0" /></html> This is the graph of data I got. The tree size goes from 1 to 500, as you can see from the graph, the max height seems to level off around 18 at a tree size of about 300.
I realised that because the data generated and stored is random<html>1</html>, we get different results everytime, instead of averaging multiple sets of data, I just took the set of data that came up once I figured out how to write the code properly (saved to a txt file, transferred the data to excel to produce the graph).
<html>1</html> This I feel is extremely weird, because we haven't seeded the rand function, we should technically be getting the same results everytime shouldn't we???
Task2
Minimum
Node* minimum( Node *node ) {
if (node == empty) {
return empty;
}
while (node->left != empty) {
node = node->left;
}
return node;
}
This is the code used for minimum - took me a while to get my head around it I had looping issues the first 10 or so attempts ><
Maximum
Node* maximum( Node *node ) {
if (node == empty) {
return empty;
}
while (node->right != empty) {
node = node->right;
}
return node;
}
This is the code used for maximum.
Problem
This is the code I used in my main function.
Node *binaryTree;
Node *min;
Node *max;
int minKey;
int maxKey;
binaryTree = empty;
min = minimum(binaryTree);
max = maximum(binaryTree);
show_tree(0, binaryTree);
printf("min key = %d, max key = %d", min->key, max->key);
The problem I had was when I tried to produce the key for an empty loop, that because the tree is empty it comes up with an error when trying to access "min->key" and "max->key" because they don't exist. Is there a way around this error???
Task3
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;
}
This is the code I came up with, it works. But I feel like this function is rather useless at this stage - when we call this function, we have to have an if statement to check whether it actually found the key we were looking for. Perhaps if we had other bits of data attached to it, this would be more useful.
Task4
Next in Preorder
Node* next_pre( Node* node ) {
if (node->left != empty) {
return node->left;
} else if (node->right != empty) {
return node->right;
} else {
if (node->parent->right != empty) {
if (node != node->parent->right) {
return node->parent->right;
}
} else {
return empty;
}
}
}
This is the code I came up with, not sure if it works properly, would've been nice if we were given some test cases to use instead of creating our own.
Previous in Preorder
Node* prev_pre( Node* node ) {
if (node->parent != empty) {
if (node == node->parent->right) {
if (node->parent->left != empty) {
return node->parent->left;
} else {
return node->parent;
}
} else {
return node->parent;
}
}
return empty;
}
Again, I'm not 100% sure if this works properly.
Task5
Node* next_in( Node* node ) {
if (node->parent != empty) {
if (node == node->parent->left) {
if (node->right != empty) {
return minimum(node->right);
} else {
return node->parent;
}
} else if (node->parent->parent != empty) {
return next_in(node->parent->parent);
}
} else {
if (node->right != empty) {
return minimum(node->right);
}
}
return empty;
}
Had to use recursion.