Mark: 12 revision(s)

2008-11-03T05:20:04Z

12 revision(s)

New page

===Task 1:===
Inserting elements in a random order. – plot height of tree vs. no. of inserted elements. Determine relationship between height and number of elements. I completed this task in a less than elegant manner, simply stacking makeRandomTree and printf statements together instead of creating a for loop. This was simple and seemed to produce similar results to everyone else – the relationship seems to be: height ~ sqrt(no. of nodes).

===Task 2:===
Node* minimum( Node* node ) {
while (node->left != empty) {
node = node->left;
}
return node;
}

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

I think these work, for min value you need to go left and for max value you need to go right. I stuffed this up a couple of times, first trying to make a new node pointer inside the functions and returning them, and then changing my while loop condition, then changing it back.

===Task 3:===
This task caught me for a bit, i consulted the 2007 HTTB and gained the understanding required to complete and (hopehully) understand the task. Here is my code:

Node* lookup( int key, Node* node ) {
if(node == empty) {
return empty;
}
if(key < node->key) {
return lookup(key, node->left);
}
else if(key > node->key) {
return lookup(key, node->right);
}
else if(key == node->key) {
return node;
}
}

I used this code to see whether or not it works, it seems to run:

Node *tree = makeRandomTree(640);
Node *max = maximum(tree);
Node *value = lookup(max->key, tree);
printf("%d is max\n%d is looked up", max->key, value->key);

returns:<br>
2145324179 is max<br>
2145324179 is looked up

===Task 4/5:===
These tasks confused me for a while and i did not figure them out before the end of the lab. i didn't think the code was too difficult to write, it just required understanding of pre and post ordering. I read task 6 and the code in the HTTB for inserting nodes into a tree, and it looked reasonably difficult. I understood it as best i could, but did not write any code as having the answer right infront of me kinda made it unfair.

SE250:lab-6:dsan039 - Revision history

Mark: 12 revision(s)