rendered paste body/* * * THIS IS A TEST FILE FOR BINARY_TREE.C * * Binary Tree Coded by Anastasios Ksouzafeiris (c) 2010 * For contact anastasis.ksouzafeiris[at]gmail[dot]com * */ #include <stdio.h>#include <stdlib.h>#include <stddef.h> #define EXIT 0#define ADD 1 #define FIND 2#define DEL 3#define SHOW 4struct node{ int data; struct node *left; struct node *right;}; struct node *root;struct node *newnode();struct node *find();struct node *insert();struct node *find_left_most();struct node *find_right_most();void display(); int main(){ int ch; int a; struct node *new; root = NULL; while(1) { printf("|0 -> Eksodos | 1 -> Add | 2 -> Find "); printf("|3 -> Delete | 4 -> Show :\n"); //ch = getchar(); scanf("%d", &ch); switch(ch) { case EXIT: return 0; case ADD: printf("num:"); scanf("%d",&a); new = insert(a); if (root == NULL) root = new; if(new == NULL) puts("Not enough memory"); break; case FIND: printf("num:"); scanf("%d",&a); new = find(a); if(new != NULL) printf("Found!\n"); else printf("There is no match!\n"); break; case DEL: printf("num:"); scanf("%d",&a); rm(a); break; default: puts("Wrong press!"); break; } }}struct node *newnode(int num){ struct node *neos; neos = malloc(sizeof(struct node)); neos->data = num; neos->left = NULL; neos->right = NULL; return(neos);} void display(struct node *ptr){ if (ptr == NULL) return; display(ptr->left); printf("%d", ptr->data); display(ptr->right);} struct node *find(int key){ struct node *current; current = root; while(current->data != key) { if(key < current->data) current = current->left; else current = current->right; if(current == NULL) return NULL; } return current;} struct node *insert(int num){ struct node *next,*current,*ptr; int isleft; next = current = root; ptr=newnode(num); if (root == NULL) { return ptr; } while(1) { if(num < current->data) { next = current->left; isleft = 1; } else { next = current->right; isleft = 0; } if(next == NULL) { if(isleft) current->left = ptr; else current->right = ptr; return ptr; } current = next; }} // Delete node with key "key"int rm(int key){ struct node *current; struct node *parent; int isLeftChild = 1; current = parent = root; while(current->data != key) { parent = current; if(key < current->data) { isLeftChild = 1; current = current->left; } else { isLeftChild = 0; current = current->right; } if(current == NULL) return 0; } // Node with key "key" found. His address is at pointer "current" // and his parent's address is at pointer "parent" // if the node does not have affiliates if(current->left == NULL && current->right == NULL) { if(current == root) // if it is root root = NULL; // the tree is blank else if(isLeftChild) parent->left = NULL; // disconnection else // from parent parent->right = NULL; } // if does not have left filial node else if(current->right == NULL) { if(current == root) root = current->left; else if(isLeftChild) parent->left = current->left; else parent->right = current->left; } // if does not have right filial node else if(current->left == NULL) { if(current == root) root = current->right; else if(isLeftChild) parent->left = current->right; else parent->right = current->right; } // if there is left & right filial node else { struct node *successor,*temp,*old_root; if(current == root) { temp = root->left; successor = find_left_most(root->right); root = root->right; successor->left = temp; } else if(isLeftChild) { successor = find_left_most(current->right); successor->left = current->left; parent->left = current->right; } else { successor = find_right_most(current->left); successor->right = current->right; parent->right = current->left; } } free(current); //releases memory allocation of the node return 1;} // identify/detect the leftmost node of the subtree rtstruct node *find_left_most(struct node *rt){ if(rt == NULL) return NULL; while(rt->left != NULL) { rt = rt->left; } return rt;} // identify/detect the rightmost node of the subtree rtstruct node *find_right_most(struct node *rt){ if(rt == NULL) return NULL; while(rt->right != NULL) { rt = rt->right; } return rt;}