Mark: 2 revision(s)

2008-11-03T05:20:06Z

2 revision(s)

New page

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

SE250:lab-6:mabd065 - Revision history

Mark: 2 revision(s)