Mark: 8 revision(s)

2008-11-03T05:20:10Z

8 revision(s)

New page

==Task 1==
After looping through 100 times, the height of the tree seen to increasing less and less while having large variation between a logarithmic graph.

<pre>
for (i = 0; i<100; i++){
x = makeRandomTree(i);
printf("size = %d height = %d\n", i, height(x));
}
</pre>

==Task 2==
Sounds easy, basically traverse through to find the right most or left most node to find the minimum or maximum
<pre>
Node* minimum( Node* node ) {
/* TODO */
while(node->left != empty){
node = node->left;
}
return node;
}

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

*However after testing the code, it seen wrong... giving me a weird number each time, I'm not sure whether it is the implementation thats wrong, or the tree is showing it wrong. The tree was REALLY and i mean REALLY hard to understand, it doesn't even look like a tree...

*After few twitching with the code, I realize I wasn't showing the correct number, and changing &y->key to y->key did the trick. (I should relearn pointers... sigh...)

==Task 3==
<pre>
Node* lookup( int key, Node* node ) {
/* TODO */
while (node != empty) {
if (key > node->key) {
node = node->right;
} else if (key < node->key) {
node = node->left;
} else {
return node;
}
}
return empty;
}
</pre>

*This was easy as well, basiclly just a set of rules and which way to go depending on whether the key is larger or smaller at current node.
==Task 4==
*Pre-order, after fiddling around through my notes, it meant traversing tree this way "root->left->right"

==Task 5==
==Task 6==

SE250:lab-6:twon069 - Revision history

Mark: 8 revision(s)