SE250:lab-6:dols008

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:

Size	Height
0	0
100	13
200	17
300	18
400	16
500	19
600	24
700	20
800	20
900	22
1000	24

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:

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

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:

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

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:

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

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.

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

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.

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

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

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

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