c6-1.c

/* code: c6-1.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;


/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;
  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;

  root = malloc (sizeof (NODE_TYPE));
  root->data = 40;

  root->left = malloc (sizeof (NODE_TYPE));
  root->left->data = 30;

  root->right = malloc (sizeof (NODE_TYPE));
  root->right->data = 70;

  root->left->left = malloc (sizeof (NODE_TYPE));
  root->left->left->data = 10;
  root->left->right = NULL;

  root->right->left = malloc (sizeof (NODE_TYPE));
  root->right->left->data = 60;
  root->right->left->left = NULL;
  root->right->left->right = NULL;

  root->right->right = malloc (sizeof (NODE_TYPE));
  root->right->right->data = 90;
  root->right->right->left = NULL;
  root->right->right->right = NULL;
  root->left->left->left = NULL;

  root->left->left->right = malloc (sizeof (NODE_TYPE));
  root->left->left->right->data = 20;
  root->left->left->right->left = NULL;
  root->left->left->right->right = NULL;


  tree_display (root, 0);
  printf ("\n");

  return 0;
}

c6-2.c

/* code: c6-2.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void traverse_preorder (NODE_TYPE * node) {
  if (node != NULL) {
    printf ("%2d ", node->data);
    traverse_preorder (node->left);
    traverse_preorder (node->right);
  }
}

/* ------------------------------------------ */
void traverse_inorder (NODE_TYPE * node) {
  if (node != NULL) {
    traverse_inorder (node->left);
    printf ("%2d ", node->data);
    traverse_inorder (node->right);
  }
}

/* ------------------------------------------ */
void traverse_postorder (NODE_TYPE * node) {
  if (node != NULL) {
    traverse_postorder (node->left);
    traverse_postorder (node->right);
    printf ("%2d ", node->data);
  }
}

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}




/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;

  root = malloc (sizeof (NODE_TYPE));
  root->data = 40;

  root->left = malloc (sizeof (NODE_TYPE));
  root->left->data = 30;

  root->right = malloc (sizeof (NODE_TYPE));
  root->right->data = 70;

  root->left->left = malloc (sizeof (NODE_TYPE));
  root->left->left->data = 10;
  root->left->right = NULL;

  root->right->left = malloc (sizeof (NODE_TYPE));
  root->right->left->data = 60;
  root->right->left->left = NULL;
  root->right->left->right = NULL;

  root->right->right = malloc (sizeof (NODE_TYPE));
  root->right->right->data = 90;
  root->right->right->left = NULL;
  root->right->right->right = NULL;
  root->left->left->left = NULL;

  root->left->left->right = malloc (sizeof (NODE_TYPE));
  root->left->left->right->data = 20;
  root->left->left->right->left = NULL;
  root->left->left->right->right = NULL;


  tree_display (root, 0);
  printf ("\n\n");


  printf ("Preorder: ");
  traverse_preorder (root);
  printf ("\n");

  printf ("Inorder:  ");
  traverse_inorder (root);
  printf ("\n");

  printf ("Postorder:");
  traverse_postorder (root);
  printf ("\n");


  return 0;
}

c6-3.c

/* code: c6-3.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;


/* ------------------------------------------ */
NODE_TYPE *tree_find_min (NODE_TYPE * node) {
  if ((node == NULL) || (node->left == NULL)) {
    return node;
  }
  return tree_find_min (node->left);
}

/* ------------------------------------------ */
NODE_TYPE *tree_find_max (NODE_TYPE * node) {
  if ((node == NULL) || (node->right == NULL)) {
    return node;
  }
  return tree_find_max (node->right);
}

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;
  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  NODE_TYPE *node_min;
  NODE_TYPE *node_max;

  root = malloc (sizeof (NODE_TYPE));
  root->data = 40;

  root->left = malloc (sizeof (NODE_TYPE));
  root->left->data = 30;

  root->right = malloc (sizeof (NODE_TYPE));
  root->right->data = 70;

  root->left->left = malloc (sizeof (NODE_TYPE));
  root->left->left->data = 10;
  root->left->right = NULL;

  root->right->left = malloc (sizeof (NODE_TYPE));
  root->right->left->data = 60;
  root->right->left->left = NULL;
  root->right->left->right = NULL;

  root->right->right = malloc (sizeof (NODE_TYPE));
  root->right->right->data = 90;
  root->right->right->left = NULL;
  root->right->right->right = NULL;
  root->left->left->left = NULL;

  root->left->left->right = malloc (sizeof (NODE_TYPE));
  root->left->left->right->data = 20;
  root->left->left->right->left = NULL;
  root->left->left->right->right = NULL;


  tree_display (root, 0);
  printf ("\n\n");

  node_min = tree_find_min (root);
  printf ("min: %d \n", node_min->data);
  node_max = tree_find_max (root);
  printf ("max: %d \n", node_max->data);
  printf ("\n");

  return 0;
}

q6-1.c

/* code: q6-1.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);

    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}

/* ------------------------------------------ */
void tree_display_r (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display_r (node->left, level + 1);

    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display_r (node->right, level + 1);
  }
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;

  root = malloc (sizeof (NODE_TYPE));
  root->data = 40;

  root->left = malloc (sizeof (NODE_TYPE));
  root->left->data = 30;

  root->right = malloc (sizeof (NODE_TYPE));
  root->right->data = 70;

  root->left->left = malloc (sizeof (NODE_TYPE));
  root->left->left->data = 10;
  root->left->right = NULL;

  root->right->left = malloc (sizeof (NODE_TYPE));
  root->right->left->data = 60;
  root->right->left->left = NULL;
  root->right->left->right = NULL;

  root->right->right = malloc (sizeof (NODE_TYPE));
  root->right->right->data = 90;
  root->right->right->left = NULL;
  root->right->right->right = NULL;
  root->left->left->left = NULL;

  root->left->left->right = malloc (sizeof (NODE_TYPE));
  root->left->left->right->data = 20;
  root->left->left->right->left = NULL;
  root->left->left->right->right = NULL;

  tree_display (root, 0);
  printf ("\n\n");

  tree_display_r (root, 0);
  printf ("\n\n");




  return 0;
}

q6-2.c

/* code: q6-2.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>


struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);

    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }

    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }

  return node;
}

/* ------------------------------------------ */
int tree_size (NODE_TYPE * node) {
  int s_left, s_right;

  if (node == NULL) {
    return 0;
  }

  s_left = tree_size (node->left);
  s_right = tree_size (node->right);

  return (s_left + s_right + 1);

}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int array[10] = { 25, 6, 49, 2, 28, 65, 51, 66, 78, 68 };


  root = NULL;
  for (i = 0; i < 10; i++) {
    root = tree_insert (root, array[i]);
  }

  tree_display (root, 0);
  printf ("\n\n");

  printf ("The number of nodes in a BST: %d\n", tree_size (root));

  return 0;
}

q6-3.c

/* code: q6-3.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>


struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);

    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }

    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }

  return node;
}

/* ------------------------------------------ */
int tree_height (NODE_TYPE * node) {
  int h_left, h_right;

  if (node == NULL) {
    return -1;
  }

  h_left = tree_height (node->left);
  h_right = tree_height (node->right);

  if (h_left > h_right) {
    return h_left + 1;
  }
  else {
    return h_right + 1;
  }
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int array[10] = { 25, 6, 49, 2, 28, 65, 51, 66, 78, 68 };


  root = NULL;
  for (i = 0; i < 10; i++) {
    root = tree_insert (root, array[i]);
  }

  tree_display (root, 0);
  printf ("\n\n");

  printf ("The height of a BST: %d\n", tree_height (root));

  return 0;
}