c8-1.c

/* code: c8-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);
  }
}


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

/* ------------------------------------------ */
void tree_delete (NODE_TYPE * node) {
  if (node == NULL)
    return;

  tree_delete (node->left);
  tree_delete (node->right);
  free (node);
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int array[10] = { 40, 30, 70, 10, 60, 90, 20, 80, 50, 100 };

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

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

  tree_delete (root);
  root = NULL;

  return 0;
}

c8-2.c

/* code: c8-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;
}

/* ------------------------------------------ */
void tree_delete (NODE_TYPE * node) {
  if (node == NULL)
    return;

  tree_delete (node->left);
  tree_delete (node->right);
  free (node);
}

/* ------------------------------------------ */
void tree_delete_wrapper (NODE_TYPE ** node) {
  tree_delete (*node);
  *node = NULL;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int array[10] = { 40, 30, 70, 10, 60, 90, 20, 80, 50, 100 };

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

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

  tree_delete_wrapper (&root);

  return 0;
}

c8-3.c

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

#define MAX_BUF 2048

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

/* ------------------------------------------ */
void print_buffer (int buf[], int len) {
  int i;
  for (i = 0; i < len; i++) {
    printf ("%d", buf[i]);
    if (i != len - 1) {
      printf (" -> ");
    }
  }
  printf ("\n");
}


/* ------------------------------------------ */
void root_to_leaf (NODE_TYPE * node, int path[], int length) {
  if (node == NULL)
    return;

  path[length] = node->data;
  length++;

  if ((node->left == NULL) && (node->right == NULL)) {
    print_buffer (path, length);
  }
  else {
    root_to_leaf (node->left, path, length);
    root_to_leaf (node->right, path, length);
  }
}


/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int array[10] = { 40, 30, 70, 10, 60, 90, 20, 80, 50, 100 };
  int *path;

  path = malloc (sizeof (int) * MAX_BUF);

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

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

  printf ("--- root-to-leaf path(s) ---\n");
  root_to_leaf (root, path, 0);

  free (path);
  return 0;
}

c8-4.c

/* code: c8-4.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;
}


/* ------------------------------------------ */
void tree_mirror (NODE_TYPE * node) {
  NODE_TYPE *temp;

  if (node != NULL) {
    tree_mirror (node->left);
    tree_mirror (node->right);

    temp = node->left;
    node->left = node->right;
    node->right = temp;
  }
}


/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int array[10] = { 40, 30, 70, 10, 60, 90, 20, 80, 50, 100 };


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

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

  printf ("--- mirror ---\n");
  tree_mirror (root);

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

  return 0;
}

q8-1.c

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

#define TRUE 1
#define FALSE 0

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_identical (NODE_TYPE * a, NODE_TYPE * b) {
  int stat;

  if ((a == NULL) && (b == NULL)) {
    return TRUE;
  }
  else if ((a != NULL) && (b != NULL)) {
    stat = (a->data == b->data) &&
      tree_identical (a->left, b->left) &&
      tree_identical (a->right, b->right);
    return stat;
  }
  else {
    return FALSE;
  }
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root_x;
  NODE_TYPE *root_y;
  int i, s;
  int array_x[5] = { 40, 30, 20, 10, 50 };
  int array_y[5] = { 40, 30, 10, 20, 50 };

  root_x = NULL;
  root_y = NULL;
  for (i = 0; i < 5; i++) {
    root_x = tree_insert (root_x, array_x[i]);
    root_y = tree_insert (root_y, array_y[i]);
  }

  tree_display (root_x, 0);
  printf ("\n\n");
  tree_display (root_y, 0);
  printf ("\n\n");

  s = tree_identical (root_x, root_y);
  if (s == TRUE) {
    printf ("identical\n");
  }
  else if (s == FALSE) {
    printf ("different\n");
  }
  return 0;
}

q8-2.c

/* code: q8-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 shuffle (int *v, int n) {
  int i, j, t;
  for (i = 0; i < n; i++) {
    j = rand () % n;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
  }
}

/* ------------------------------------------ */
void rand_nd (int *v, int n) {
  int i;

  for (i = 0; i < n; i++) {
    v[i] = i;
  }
  shuffle (v, n);
}

/* ------------------------------------------ */
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 main () {
  NODE_TYPE *root;
  int i, n;
  int *v;

  root = NULL;
  v = NULL;
  n = 1000;

  srand (1);

  v = malloc (sizeof (int) * n);

  rand_nd (v, n);

  for (i = 0; i < n; i++) {
    root = tree_insert (root, v[i]);
  }

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

  free (v);
  return 0;
}

q8-3.c

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

struct node_type {
  int data;
  int height;
  struct node_type *left;
  struct node_type *right;
};
typedef struct node_type NODE_TYPE;

/* ------------------------------------------ */
void shuffle (int *v, int n) {
  int i, j, t;
  for (i = 0; i < n; i++) {
    j = rand () % n;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
  }
}

/* ------------------------------------------ */
void rand_nd (int *v, int n) {
  int i;

  for (i = 0; i < n; i++) {
    v[i] = i;
  }
  shuffle (v, n);
}

/* ------------------------------------------ */
int avl_max (int x, int y) {
  return (x > y) ? x : y;
}

/* ------------------------------------------ */
int avl_height (NODE_TYPE * node) {
  if (node == NULL) {
    return 0;
  }
  return node->height;
}

/* ------------------------------------------ */
NODE_TYPE *avl_newnode (int data) {
  NODE_TYPE *node;

  node = malloc (sizeof (NODE_TYPE));
  node->data = data;
  node->height = 1;
  node->left = NULL;
  node->right = NULL;
  return (node);
}

/* ------------------------------------------ */
NODE_TYPE *avl_right_r (NODE_TYPE * node_b) {
  NODE_TYPE *node_a;
  NODE_TYPE *temp_node;

  node_a = node_b->left;
  temp_node = node_a->right;
  node_a->right = node_b;
  node_b->left = temp_node;

  node_b->height =
    avl_max (avl_height (node_b->left), avl_height (node_b->right)) + 1;
  node_a->height =
    avl_max (avl_height (node_a->left), avl_height (node_a->right)) + 1;

  return node_a;
}

/* ------------------------------------------ */
NODE_TYPE *avl_left_r (NODE_TYPE * node_a) {
  NODE_TYPE *node_b;
  NODE_TYPE *temp_node;

  node_b = node_a->right;
  temp_node = node_b->left;
  node_b->left = node_a;
  node_a->right = temp_node;

  node_a->height =
    avl_max (avl_height (node_a->left), avl_height (node_a->right)) + 1;
  node_b->height =
    avl_max (avl_height (node_b->left), avl_height (node_b->right)) + 1;

  return node_b;
}


/* ------------------------------------------ */
int avl_height_diff (NODE_TYPE * node) {
  int diff;

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

  diff = avl_height (node->left) - avl_height (node->right);
  return diff;
}


/* ------------------------------------------ */
NODE_TYPE *avl_insert (NODE_TYPE * node, int data) {
  int diff;
  if (node == NULL) {
    return (avl_newnode (data));
  }
  if (data < node->data) {
    node->left = avl_insert (node->left, data);
  }
  else {
    node->right = avl_insert (node->right, data);
  }

  node->height =
    avl_max (avl_height (node->left), avl_height (node->right)) + 1;

  diff = avl_height_diff (node);

  if ((diff > 1) && (data < node->left->data)) {
    return avl_right_r (node);
  }

  if ((diff < -1) && (data > node->right->data)) {
    return avl_left_r (node);

  }

  if ((diff > 1) && (data > node->left->data)) {
    node->left = avl_left_r (node->left);
    return avl_right_r (node);
  }

  if ((diff < -1) && (data < node->right->data)) {
    node->right = avl_right_r (node->right);
    return avl_left_r (node);
  }

  return node;
}



/* ------------------------------------------ */
NODE_TYPE *avl_node_min (NODE_TYPE * node) {
  NODE_TYPE *temp_node;

  temp_node = node;
  while (temp_node->left != NULL) {
    temp_node = temp_node->left;
  }
  return temp_node;
}


/* ------------------------------------------ */
NODE_TYPE *deleteNode (NODE_TYPE * root, int data) {
  int diff;

  if (root == NULL) {
    return root;
  }
  if (data < root->data) {
    root->left = deleteNode (root->left, data);
  }
  else if (data > root->data) {
    root->right = deleteNode (root->right, data);
  }
  else {
    if ((root->left == NULL) || (root->right == NULL)) {
      NODE_TYPE *temp = root->left ? root->left : root->right;
      if (temp == NULL) {
	temp = root;
	root = NULL;
      }
      else {
	*root = *temp;
      }
      free (temp);
    }
    else {
      NODE_TYPE *temp = avl_node_min (root->right);
      root->data = temp->data;
      root->right = deleteNode (root->right, temp->data);
    }
  }


  if (root == NULL) {
    return root;
  }
  root->height =
    avl_max (avl_height (root->left), avl_height (root->right)) + 1;

  diff = avl_height_diff (root);
  if ((diff > 1) && (avl_height_diff (root->left) >= 0)) {
    return avl_right_r (root);
  }

  if ((diff > 1) && (avl_height_diff (root->left) < 0)) {
    root->left = avl_left_r (root->left);
    return avl_right_r (root);
  }

  if ((diff < -1) && (avl_height_diff (root->right) <= 0)) {
    return avl_left_r (root);
  }

  if ((diff < -1) && (avl_height_diff (root->right) > 0)) {
    root->right = avl_right_r (root->right);
    return avl_left_r (root);
  }

  return root;
}

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

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



/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, n;
  int *v;

  root = NULL;
  v = NULL;
  n = 1000;

  srand (1);

  v = malloc (sizeof (int) * n);

  rand_nd (v, n);

  srand (1);
  for (i = 0; i < n; i++) {
    root = avl_insert (root, v[i]);
  }

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

  free (v);

  return 0;
}

q8-4.c

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

struct node_type {
  int data;
  int height;
  struct node_type *left;
  struct node_type *right;
};
typedef struct node_type NODE_TYPE;

/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}

/* ------------------------------------------ */
void shuffle (int *v, int n) {
  int i, j, t;
  for (i = 0; i < n; i++) {
    j = rand () % n;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
  }
}

/* ------------------------------------------ */
void rand_nd (int *v, int n) {
  int i;

  for (i = 0; i < n; i++) {
    v[i] = i;
  }
  shuffle (v, n);
}

/* ------------------------------------------ */
int avl_max (int x, int y) {
  return (x > y) ? x : y;
}

/* ------------------------------------------ */
int avl_height (NODE_TYPE * node) {
  if (node == NULL) {
    return 0;
  }
  return node->height;
}

/* ------------------------------------------ */
NODE_TYPE *avl_newnode (int data) {
  NODE_TYPE *node;

  node = malloc (sizeof (NODE_TYPE));
  node->data = data;
  node->height = 1;
  node->left = NULL;
  node->right = NULL;
  return (node);
}

/* ------------------------------------------ */
NODE_TYPE *avl_right_r (NODE_TYPE * node_b) {
  NODE_TYPE *node_a;
  NODE_TYPE *temp_node;

  node_a = node_b->left;
  temp_node = node_a->right;
  node_a->right = node_b;
  node_b->left = temp_node;

  node_b->height =
    avl_max (avl_height (node_b->left), avl_height (node_b->right)) + 1;
  node_a->height =
    avl_max (avl_height (node_a->left), avl_height (node_a->right)) + 1;

  return node_a;
}

/* ------------------------------------------ */
NODE_TYPE *avl_left_r (NODE_TYPE * node_a) {
  NODE_TYPE *node_b;
  NODE_TYPE *temp_node;

  node_b = node_a->right;
  temp_node = node_b->left;
  node_b->left = node_a;
  node_a->right = temp_node;

  node_a->height =
    avl_max (avl_height (node_a->left), avl_height (node_a->right)) + 1;
  node_b->height =
    avl_max (avl_height (node_b->left), avl_height (node_b->right)) + 1;

  return node_b;
}


/* ------------------------------------------ */
int avl_height_diff (NODE_TYPE * node) {
  int diff;

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

  diff = avl_height (node->left) - avl_height (node->right);
  return diff;
}


/* ------------------------------------------ */
NODE_TYPE *avl_insert (NODE_TYPE * node, int data) {
  int diff;
  if (node == NULL) {
    return (avl_newnode (data));
  }
  if (data < node->data) {
    node->left = avl_insert (node->left, data);
  }
  else {
    node->right = avl_insert (node->right, data);
  }

  node->height =
    avl_max (avl_height (node->left), avl_height (node->right)) + 1;

  diff = avl_height_diff (node);

  if ((diff > 1) && (data < node->left->data)) {
    return avl_right_r (node);
  }

  if ((diff < -1) && (data > node->right->data)) {
    return avl_left_r (node);

  }

  if ((diff > 1) && (data > node->left->data)) {
    node->left = avl_left_r (node->left);
    return avl_right_r (node);
  }

  if ((diff < -1) && (data < node->right->data)) {
    node->right = avl_right_r (node->right);
    return avl_left_r (node);
  }

  return node;
}



/* ------------------------------------------ */
NODE_TYPE *avl_node_min (NODE_TYPE * node) {
  NODE_TYPE *temp_node;

  temp_node = node;
  while (temp_node->left != NULL) {
    temp_node = temp_node->left;
  }
  return temp_node;
}


/* ------------------------------------------ */
NODE_TYPE *deleteNode (NODE_TYPE * root, int data) {
  int diff;

  if (root == NULL) {
    return root;
  }
  if (data < root->data) {
    root->left = deleteNode (root->left, data);
  }
  else if (data > root->data) {
    root->right = deleteNode (root->right, data);
  }
  else {
    if ((root->left == NULL) || (root->right == NULL)) {
      NODE_TYPE *temp = root->left ? root->left : root->right;
      if (temp == NULL) {
	temp = root;
	root = NULL;
      }
      else {
	*root = *temp;
      }
      free (temp);
    }
    else {
      NODE_TYPE *temp = avl_node_min (root->right);
      root->data = temp->data;
      root->right = deleteNode (root->right, temp->data);
    }
  }


  if (root == NULL) {
    return root;
  }
  root->height =
    avl_max (avl_height (root->left), avl_height (root->right)) + 1;

  diff = avl_height_diff (root);
  if ((diff > 1) && (avl_height_diff (root->left) >= 0)) {
    return avl_right_r (root);
  }

  if ((diff > 1) && (avl_height_diff (root->left) < 0)) {
    root->left = avl_left_r (root->left);
    return avl_right_r (root);
  }

  if ((diff < -1) && (avl_height_diff (root->right) <= 0)) {
    return avl_left_r (root);
  }

  if ((diff < -1) && (avl_height_diff (root->right) > 0)) {
    root->right = avl_right_r (root->right);
    return avl_left_r (root);
  }

  return root;
}

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

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



/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, n;
  int *v;

  root = NULL;
  v = NULL;
  n = 100;

  srand (1);

  v = malloc (sizeof (int) * n);

  rand_nd (v, n);

  qsort (v, n, sizeof (int), int_compare);

  for (i = 0; i < n; i++) {
    root = avl_insert (root, v[i]);
  }

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

  free (v);

  return 0;
}