SE250:lab-6:dcho040

Code

tree.h

/*
  File:    tree.h
  Date:    3 April 2007 (last modified by Mark Wilson 5 May 2008)
  Author:  John Hamer (trivial modifications by Mark Wilson)
  Purpose: Code resource for SOFTENG 250 lab #6
*/

typedef
struct Node {
  int key;
  struct Node *left;
  struct Node *right;
  struct Node *parent;		/* ADDED */
} Node;


Node *mkNode( int key, Node* parent );
void insert( int key, Node **node );
void show_tree( int level, Node* node );
Node* minimum( Node* node );
Node* maximum( Node* node );
Node* lookup( int key, Node* node );
Node* next_pre( Node* node );
Node* prev_pre( Node* node );
Node* next_in( Node* node );
Node* prev_in( Node* node );
Node* next_post( Node* node );
Node* prev_post( Node* node );
Node* insertMinHeight( int n);
Node* makeRandomTree( int size );
int Max( int x, int y );
int height( Node* node );

tree.c

/*
  File:    tree.c
  Date:    3 April 2007 (last modified by Mark Wilson 5 May 2008)
  Author:  John Hamer (trivial modifications by Mark Wilson)
  Purpose: Code resource for SOFTENG 250 lab #6
*/

#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

Node *empty = (Node*)0, *before; /* pointer to "external node" */
int search = 1, compareKey=-1;

Node *mkNode( int key, Node* parent ) {	/* CHANGED */
  Node *newn = (Node*)malloc( sizeof(Node) );
  if( ! newn ) {
    fprintf( stderr, "! Out of memory\n" );
    exit( 1 );
  }
  newn->key    = key;
  newn->left   = empty;
  newn->right  = empty;
  newn->parent = parent;	/* ADDED */
  return newn;
}

/* CHANGED */
void insert( int key, Node **node ) {
  Node* parent = empty;
  while( *node != empty ) {
    parent = *node;
    if( key < (*node)->key )
      node = &(*node)->left;
    else
      node = &(*node)->right;
  }
  *node = mkNode( key, parent );
}

void show_tree( int level, Node* node ) {
  if( node == empty )
    return;

  show_tree( level+1, node->left );
  printf( "%*s%d [%d]\n", level*2, "", node->key, level );
  show_tree( level+1, node->right );
}


Node* minimum( Node* node ) {
  if ((node == empty) | (node->left == empty))
    return node;
  return minimum(node->left);
}

Node* maximum( Node* node ) {
  if ((node == empty) | (node->right == empty))
    return node;
  return maximum(node->right);
}

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

Node* next_pre( Node* node ) {
  if (node != empty) {
    if (node->left != empty)
      return node->left;
    before = empty;
    while (node != empty) {
      if ((node->right != empty) && (node->right != before))
	return node->right;
      before = node;
      node = node->parent;
    }
  }
  return empty;
}

Node* prev_pre( Node* node ) {
  if ((node == empty) || (node->parent == empty))
    return empty;
  if (((node->parent)->left == node) | ((node->parent)->left == empty))
    return node->parent;
  node = (node->parent)->left;
  search = 1;
  while (search){
    if (node->right != empty)
      node = node->right;
    else if (node->left != empty)
      node = node->left;
    else
      search = 0;
  }
  return node;
}

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;
  }
  do {
    before = node;
    node = node->parent;
    if (node == empty)
      return empty;
  } while (node->left != before);
  return node;
}

Node* prev_in( Node* node ) {
  if (node == empty)
    return empty;
  if (node->left != empty) {
    node = node->left;
    while(node->right != empty)
      node = node->right;
    return node;
  }
  do{
    before = node;
    node = node->parent;
    if (node == empty)
      return empty;
  } while (node->left == before);
  return node;
}

Node* next_post( Node* node ) {
  if ((node == empty) || (node->parent == empty))
    return empty;
  before = node;
  node = node->parent;
  if ((node->right == before) | (node->right == empty))
    return node;
  node = node->right;
  search = 1;
  while(search) {
    if (node->left != empty)
      node = node->left;
    else if (node->right != empty)
      node = node->right;
    else
      search = 0;
  }
  return node;
}

Node* prev_post( Node* node ) {
  if (node == empty)
    return node;
  if (node->right != empty)
    return node->right;
  do {
    if (node->left != empty)
      return node->left;
    before = node;
    node = node->parent;
    if (node == empty)
      return empty;
  } while(node->right == before);
  do{
    before = node;
    node = node->parent;
    if (node == empty)
      return empty;
  } while (node->left == before);
  if (node->left != empty)
    return node->left;
  return node;
}

Node* insertMinHeight( int n) {
  if (n < 1){
    printf("n should be a integer bigger than 0");
    return empty;
  }
  Node *root = empty;
  bestTree(1, n, &root);
  return root;
}

void bestTree(int start, int end, Node **root) {  
  if (start == end) {
    insert(start, root);
    return ;
  }
  if (start+1 == end) {
    insert(start, root);
    insert(end, root);
    return ;
  }
  int middle = (start + end) / 2;
  insert(middle, root);
  bestTree(start, middle-1, root);
  bestTree(middle+1, end, root);
  return;
}

Node* makeRandomTree( int size ) {
  Node* root = empty;
  while( size-- > 0 )
    insert( rand( ), &root );
  return root;
}

int Max( int x, int y ) {
  if( x > y )
    return x;
  else
    return y;
}

/* Length of the longest path from node to a leaf */
int height( Node* node ) {
  if( node == empty )
    return 0;
  else
    return Max( height( node->left ),
		height( node->right ) ) + 1;
}

lab6.c

#include<stdio.h>
#include"tree.h"

int main() {
  Node *test, *maxNode, *minNode, *lookedNode;
  int heightTree, i;
  Node *empty = (Node*)0;  

  //task 1
  printf("\ntask1\n");
  for (i = 1; i <= 20; i++) {
    test = makeRandomTree( i*50 );
    heightTree = height( test );
    printf("inputs height: %d %d\n",i*50, heightTree);
  }

  //task 2
  printf("\ntask2\n");
  test = makeRandomTree(10);
  printf("show_tree\n");
  show_tree(1, test);

  minNode = minimum(test);
  maxNode = maximum(test);
  printf("minimum: %d\n",minNode->key);
  printf("maximum: %d\n",maxNode->key);

  //task 3
  printf("\ntask3\n");
  lookedNode = lookup(maxNode->key, test);
  printf("find maxNode's key from task3\n"
	 "So two addresses should be the same\n"
	 "maxNode's address: %p \nlookedNod's address: %p\n"
	 , maxNode, lookedNode);
  
  lookedNode = lookup(10, test);
  printf("looked the key not in the tree : %p\n",lookedNode);


  //task 4 & 5
  printf("\ntask4&5\n");
  printf("test model\n"
	 "      10\n"
	 "  3        13\n"
	 "2   7   12    15\n"
	 "   6 9      14\n"
	 "  4\n"
	 "   5\n");
  Node *root = empty;
  insert( 10, &root );
  insert( 3, &root );
  insert( 13, &root );
  insert( 2, &root );
  insert( 7, &root );
  insert( 12, &root );
  insert( 15, &root );
  insert( 6, &root );
  insert( 9, &root );
  insert( 14, &root );
  insert( 4, &root );
  insert( 5, &root );
  Node *nowNode = root;
  printf("next_pre\n");
  while (nowNode != empty) {
    printf("%d\n",(nowNode->key));
    nowNode = next_pre(nowNode);
  }
  printf("prev_pre\n");
  nowNode = lookup(14,root);
  while (nowNode != empty) {
    printf("%d\n",(nowNode->key));
    nowNode = prev_pre(nowNode);
  }
  printf("next_in\n");
  nowNode = lookup(2,root);
  while (nowNode != empty) {
    printf("%d\n",(nowNode->key));
    nowNode = next_in(nowNode);
  }
  printf("prev_in\n");
  nowNode = lookup(15,root);
  while (nowNode != empty) {
    printf("%d\n",(nowNode->key));
    nowNode = prev_in(nowNode);
  }
  printf("next_post\n");
  nowNode = lookup(2,root);
  while (nowNode != empty) {
    printf("%d\n",(nowNode->key));
    nowNode = next_post(nowNode);
  }
  printf("prev_post\n");
  nowNode = root;
  while (nowNode != empty) {
    printf("%d\n",(nowNode->key));
    nowNode = prev_post(nowNode);
  }
  
  //task 6
  printf("\ntask6\n");
  test = insertMinHeight( 127 );
  printf("insert 1 to 63 => height should be 7 : %d", height(test));
  return 0;
}

result

task1
inputs height: 50 9
inputs height: 100 11
inputs height: 150 14
inputs height: 200 17
inputs height: 250 17
inputs height: 300 20
inputs height: 350 20
inputs height: 400 18
inputs height: 450 18
inputs height: 500 22
inputs height: 550 17
inputs height: 600 17
inputs height: 650 20
inputs height: 700 21
inputs height: 750 20
inputs height: 800 22
inputs height: 850 19
inputs height: 900 22
inputs height: 950 24
inputs height: 1000 25

task2
show_tree
      275604784 [3]
        316933620 [4]
          506157045 [5]
    517422363 [2]
        954301386 [4]
      1607502745 [3]
        1636059385 [4]
  1852094467 [1]
      1903092272 [3]
    2011631455 [2]
minimum: 275604784
maximum: 2011631455

task3
find maxNode's key from task3
So two addresses should be the same
maxNode's address: 0x80888b0 
lookedNod's address: 0x80888b0
looked the key not in the tree : (nil)

task4&5
test model
      10
  3        13
2   7   12    15
   6 9      14
  4
   5
next_pre
10
3
2
7
6
4
5
9
13
12
15
14
prev_pre
14
15
12
13
9
5
4
6
7
2
3
10
next_in
2
3
4
5
6
7
9
10
12
13
14
15
prev_in
15
14
13
12
10
9
7
6
5
4
3
2
next_post
2
5
4
6
9
7
3
12
14
15
13
10
prev_post
10
13
15
14
12
3
7
9
6
4
5
2

task 6
insert 1 to 63 => height should be 7 : 7

discussion

this lab is very easy to have a mistake.

It took about 10 hours to finish all tasks.

first I change lab6.c to tree.c and tree.h

and create main file lab6.c to test all functions written in tree.c

• task 1: I just display the inputs and height but it is quite clear that the heights is showing quite random but if we look at the out line, the degree of the graph decreases by increasing the inputs.

• task 2: this function is to finding leftest or rightest value and lab6.c test this function by using one example of tree.

• task 3: lab6.c test two things that the function finds key or not. using the example tree from task 2.

• task 4,5: they were most tricky because there are a lot of conditions have to deal with. lab6.c creates one complex example and display all next, prev functions from start to the end.

• task 6: Idea of this task was to input the middle value first. this question is easily solved by calling the function inside of the function.