SE250:lab-6:llay008
Task One
Task one was straightforward. I had no major problems with this other than some small syntactical errors in my code that were easily remedied and the fact that it seemed to take a long time...
an excerpt from my code:-
for (size = 10; size < maxSize ; size+=10) { for(i = 0; i < n; i++) { randomTree = makeRandomTree(size); treeHeight += height(randomTree); } aveHeight = treeHeight/n; printf("size = %d average heigth = %f\n", size, aveHeight); }
This gave the output:-
size = 10 average heigth = 5.640000 size = 20 average heigth = 13.440000 size = 30 average heigth = 22.370000 size = 40 average heigth = 32.300000 size = 50 average heigth = 43.070000 size = 60 average heigth = 54.530000 size = 70 average heigth = 66.970000 size = 80 average heigth = 79.490000 size = 90 average heigth = 92.230000
The relationship appears to be that the larger the tree, longer the the height in relation to the tree size. I plotted a graph but was unsure how to load it on to the wiki.
Edit: I later realised that these results are erroneous because I forgot to set the average height back to 0.
State4Plasma was here... *height* you mean? ;p (just mucking around a bit XD)
Task Two
This again was straightforward. My code is as follows:-
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; }
Task Three
After getting off onto the wrong track (for only a short time luckily) by forgetting about the properties of empty, I created this code:-
Node* lookup( int key, Node* node ) { while ((key != node-> key) && (node != empty)) { if (key >= node->right) { node = node->right; } if (key < node->left) { node = node->left; } } return node; }