SE250:lab-6:mabd065
Jump to navigation
Jump to search
The first thing i did was looking at the code.
Task1
After i understod the makeRandomTree() and show_tree() i wrote the following code:
int main() {
int i = 0;
for ( ; i < 4; i++) {
show_tree(0, makeRandomTree(100));
printf("------------\n\n");
}
return 0;
}
The code prints 4 random trees each time i change the number of nodes in a rendom tree. I varied the number of nodes
between 10 and a 100.
Size Trial1 Trial2 Trial3 Trial4 Average Height 10 5 5 3 4 4 20 8 6 8 6 7 30 9 9 8 7 8 40 9 8 11 9 9 50 10 8 8 10 9 60 10 10 10 9 10 70 12 10 9 12 11 80 12 12 10 11 11 90 12 14 9 13 12 100 12 13 15 13 13
Ploting the size vs the Average Height gives the following graph: <HTML> <img src="http://img377.imageshack.us/img377/5729/image001gc2.png" border="0" /> </HTML> Looking at the graph, it looks like it is a liner relationship. As the number of nodes grows,
Task2
The Minimum function:
Node* minimum( Node* node ) {
while (node->left != empty)
node = node->left;
return node;
}
The Maximum function:
Node* maximum( Node* node ) {
while (node->right != empty)
node = node->right;
return node;
}
To test it, i have used the following:
int main() {
Node *newBST;
newBST = makeRandomTree(5);
show_tree(0, newBST);
printf("Minimum: %d\n", minimum(newBST)->key);
printf("Maximum: %d", maximum(newBST)->key);
return 0;
}