Mark: 7 revision(s)

2008-11-03T05:20:04Z

7 revision(s)

New page

===Task 1===
To determine the relationship between tree size and height, I decided to loop through a number of different tree sizes. For each tree size I would generate a random binary tree and record it's height. Here is some sample data:
<pre>Size Height
0 0
100 13
200 17
300 18
400 16
500 19
600 24
700 20
800 20
900 22
1000 24</pre>
To make my data more accurate, I decided to generate a number of trees of any particular size and average the heights. Here are the results after averaging 10 trees per size:
<pre>Size Height
0 0.000000
100 13.400000
200 16.000000
300 17.800000
400 18.400000
500 19.700000
600 20.100000
700 20.800000
800 20.700000
900 21.600000
1000 22.100000</pre>

I was disappointed to find that there is no given method for freeing binary trees.

===Task 2===
Implementing the minimum and maximum functions was straight forward, but testing them was a little tricky. I opted to do it by generating a few random trees, printing them out using show_tree and visually checking my minimum and maximum were correct. The output of show_tree was less than intuitive, it took me a while to figure out the tree is actually sideways. I also found that the root of my tree always had a key of 0, so I seeded rand() to get some more interesting data.

Here is my code for minimum and maximum:
<pre>Node* minimum( Node* node ) {
if (node != empty && node->left != empty)
return minimum(node->left);
return node;
}

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

===Task 3===
Lookup wasn't hard either, but again it was a pain to test. I had to construct the tree by hand this time so that I knew which numbers were in it (though it occurs to me now I could have used the same seed each time). Here's the code:
<pre>Node* lookup( int key, Node* node ) {
if (node == empty || key == node->key)
return node;
if (key > node->key)
return lookup(key, node->right);
else
return lookup(key, node->left);
}</pre>

===Task 4/5===
Preorder took a fair bit of thought. It didn't seem hard at first, but it took a couple of broken versions which got stuck down leaves before I got it right. Once I had a working version I tidied it up a bit and removed an extra variable.
<pre>Node* next_pre( Node* node ) {
if (node == empty)
return empty;
if (node->left != empty)
return node->left;
if (node->right != empty)
return node->right;
while (node->parent != empty)
{
if (node->parent->right != empty && node->parent->right != node)
return node->parent->right;
node = node->parent;
}
return empty;
}</pre>

I skipped ahead to next_in, because it seemed more interesting. This one took a couple of tries too. There's less in common between the functions than I expected.

<pre>Node* next_in( Node* node ) {
if (node == empty)
return empty;
if (node->right != empty)
{
node = node->right;
while (node->left != empty)
node = node->left;
return node;
}
while (node->parent && node->parent->right == node)
node = node->parent;
return node->parent;
}</pre>

It's not getting much easier. next_post took some figuring out too.

<pre>Node* next_post( Node* node ) {
if (node == empty || node->parent == empty)
return empty;
if (node->parent->right != empty && node->parent->right != node)
{
node = node->parent->right;
while (node->left != empty)
node = node->left;
while (node->right != empty)
node = node->right;
return node;
}
return node->parent;
}</pre>

I'm well over time now. I might come back to this later, it's good practice.

SE250:lab-6:dols008 - Revision history

Mark: 7 revision(s)