Mark: 10 revision(s)

2008-11-03T05:20:04Z

10 revision(s)

New page

==Task 1==

int main(void) {

Node *initial;
int i = 0;
for (i; i < 51; i++) {
initial = makeRandomTree(i);

printf("%d\n", height(initial));
}

}

I struggled initially to find out how to make a tree, but then I realized that there was the makeRandomTree function! >_< Since we had to plot a graph, I decided to plot up to 50 points to see what the graph would look like. Probably should of plotted more or made it increment by 5 every time...but I had already moved on by the time I realized this. This is what I analyzed from the graph:

- I used a scatter plot graph

- Since it was a random tree, it meant that just because the size increased doesn't mean the height increases, sometimes it would decrease. This is just due to how the tree is made and where the nodes are inserted I presume.

- There was still however a noticeable upward curve, even though it was a slow increase.

[http://www.geocities.com/braydondunnit/graph.jpg Graph]

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

}
}

To find the minimum, it must be on the left most side of the tree, and for maximum it must be on the right most side. This is why for minimum I had node = node->left and for maximum I had node = node->right. Originally had trouble figuring out whether my huge values were right: e.g.

The minimum value of the tree is: 2309112
The maximum value of the tree is: 2309136

But figured that since its a random tree, it probably wouldn't be much of a surprise. As long as the maximum is greater than the minimum I was satisfied. For now.

==Task 3==
Having lots of trouble figuring out how to make a tree so that I know specifically what values there are so I can check whether my function works or not. I've written the function so far:

Node* lookup( int key, Node* node ) {
if (node == empty) {
return node;
}

while (node != empty) {
if (key == node->key)
return node;
else if (key > node->key)
node = node->right;
else
node = node->left;
}
}

But need to test it to make sure it works.

==Task 4==
I have no idea what's going on..at this rate I've given up, will try to finish later.

Node* next_pre( Node* node ) {
if (node->left != empty)
return next_pre(node->left)

if (node->right != empty)
return next_pre(node->right)
}

==Task 5==

==Task 6==

SE250:lab-6:gfun006 - Revision history

Mark: 10 revision(s)