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