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