[C] Binary Search Tree

2003 Fall / 화일처리 / 이석호 교수님

/**

Binary Search Tree

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include <stdio.h>

struct znode                        // binary search tree node
{
       int data;                        // data type is integer
       struct znode * left;                        // left subtree
       struct znode * right;                        // right subtree
};

struct znode * root = NULL;                        // root node, initially NULL

void print_tree_inorder(struct znode* tree)       // print tree in inorder (left -> parent -> right)
{
       if (tree == NULL)
               printf("Tree is empty!\n");
       else
       {
               if (tree->left != NULL)
                       print_tree_inorder(tree->left);
               printf("%d ", tree->data);
               if (tree->right != NULL)
                       print_tree_inorder(tree->right);
       }
}

struct znode* insert(int insert_data, struct znode* tree)                // node insert
{
       if (tree == NULL)                  // if null, make new node
       {
               tree = (struct znode *)malloc(sizeof(struct znode));
               tree->data = insert_data;
               tree->left = NULL;
               tree->right = NULL;
       }
       else if (insert_data < tree->data)                // insert data in left subtree
               tree->left = insert(insert_data, tree->left);
       else if (insert_data > tree->data)
               tree->right = insert(insert_data, tree->right);         // insert data in right subtree
       else
               printf("Insert Error : item duplicated!\n");        // when the item already exists

       return tree;
}

struct znode* zremove_min(struct znode* tree)          // delete minimum-valued node
{
       struct znode* temp = tree;

       if (tree == NULL)
               printf("remove Minimum Error : null tree!\n");
       else if (tree->left != NULL)
               tree->left = zremove_min(tree->left);              // traverse to left and left again
       else
       {
               tree = tree->right;                   // attach right subtree(or NULL) to parent
               free(temp);                               // and remove the old parent
       }

       return tree;
}

struct znode* zremove(int remove_data, struct znode* tree)           // delete node
{
       struct znode* temp = tree;

       if (tree == NULL)
               printf("remove Error : item not found!\n");
       else if (remove_data < tree->data)            // delete data in left subtree
               tree->left = zremove(remove_data, tree->left);
       else if (remove_data > tree->data)
               tree->right = zremove(remove_data, tree->right);   // delete data in right subtree
       else if (tree->left != NULL && tree->right != NULL)
                                // if this has both left and rihgt subtree
       {
               temp = temp->right;
               while (temp->left != NULL)
                       temp = temp->left;             // find the minimum data of right subtree
               tree->data = temp->data;                      // and set it to the parent
               tree->right = zremove_min(tree->right);     // and remove it in right subtree
       }
       else
       {
               tree = (tree->left != NULL) ? tree->left : tree->right;
                         // attach one of two children to parent (tree or NULL)
               free(temp);                                // free the old parent
       }

       return tree;
}

int main()
{
       FILE* fp;
       char buffer[11];

       fp = fopen("index.txt", "r");
       while (fgets(buffer, 10, fp) != NULL)                  // read one line from index.txt
       {
               printf("\ninsert %d : ", atoi(buffer));
               root = insert(atoi(buffer), root);                  // insert it
               print_tree_inorder(root);                              // and print the current tree shape
       }
       fclose(fp);

       fp = fopen("index.txt", "r");                             // close and reopen
       while (fgets(buffer, 10, fp) != NULL)
       {
               printf("\ndelete %d : ", atoi(buffer));
               root = zremove(atoi(buffer), root);               // delete a node
               print_tree_inorder(root);                              // and print
       }
       fclose(fp);

       return 0;
}

/**

Binary Search Tree

zzun
hello82@unitel.co.kr
http://zzun.net

**/