Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #define bigNum ~(1<<31)
- typedef struct Data {
- int id;
- char name[];
- }Data;
- typedef struct Node{
- Data data;
- struct Node *left, *right;
- }Node;
- typedef Node Tree;
- Node * newNode(int id){
- Node* node = malloc(sizeof(Node));
- node->data.id = id;
- node->left = node->right = NULL;
- return node;
- }
- Node * addRight(Node *root,int id){
- if(root) {
- Node* new = newNode(id);
- root->right = new;
- return new;
- }
- return NULL;
- }
- Node * addLeft(Node *root,int id){
- if(root) {
- Node* new = newNode(id);
- root->left = new;
- return new;
- }
- return NULL;
- }
- // START OF TRAVERSING FUNCTIONS.
- void preTravers(Tree *root){
- if(root) {
- printf("[%d]\n", root->data.id);
- preTravers(root->left);
- preTravers(root->right);
- }
- }
- void postTravers(Tree *root){
- if(root) {
- postTravers(root->left);
- postTravers(root->right);
- printf("[%d]\n", root->data.id);
- }
- }
- void inTravers(Tree *root){
- if(root) {
- inTravers(root->left);
- printf("[%d]\n", root->data.id);
- inTravers(root->right);
- }
- }
- // END OF TRAVERSING FUNCTIONS.
- // START SHOWING FUNCTIONS.
- void inShow(Tree *root,int currentDepth){
- if(root && root->data.id != ~(1<<31)) {
- inShow(root->right,currentDepth+1);
- int i; for(i=0;i<currentDepth;i++) printf("\t");
- printf("%3d::%p ", root->data.id,root);
- inShow(root->left,currentDepth+1);
- }else
- printf("\n");
- }
- // END SHOWING FUNCTIONS.
- // START OF INSERTING IN BST FUNCTION.
- void insert(Tree *root,int id){
- Node * node = newNode(id);
- if(root) {
- if(id < root->data.id ){
- // GO LEFT
- // if there is no left node
- if(!root->left)
- root->left = node;
- else // there is a node insert to it
- insert(root->left,id);
- }else{
- // GO RIGHT
- // if there is no right node
- if(!root->right)
- root->right = node;
- else
- insert(root->right,id);
- }
- }
- // return node;
- }
- // END OF INSERTING IN BST FUNCTION.
- // START OF FUNCTION TO GET SMALLEST ELEMENT.
- Node * getSmallest(Tree *root){
- if(root->left || root->right) {
- if(root->left) return getSmallest(root->left);
- if(root->right && !root->left) return root;
- }
- return root;
- }
- // END OF FUNCTION TO GET SMALLEST ELEMENT.
- // START OF SEARCHING IN BST FUNCTION.
- Node * search (Tree *root,int id){
- if (!root)
- return NULL;
- if (root->data.id == id)
- return root;
- if (id < root->data.id)
- return search(root->left,id);
- else
- return search(root->right,id);
- }
- // END OF SEARCHING IN BST FUNCTION.
- // START OF FUNCTION TO GET PARENT OF NODE.
- Node * getParent(Tree *root,Node *node){
- if(root) {
- if(root->left == node || root->right == node) {
- return root;
- }else{
- if(node->data.id < root->data.id)
- root = root->left;
- else
- root = root->right;
- return getParent(root,node);
- }
- }
- return NULL;
- }
- // NED OF FUNCTION TO GET PARENT OF NODE.
- // START OF DELETING FROM BST FUNCTION.
- /*
- void delete(Tree *root,Node *parent,Node *node){
- if(root) {
- if(root==node){ // WE ARE AT THE NODE BEGIN DELETE OPERATION
- if(!node->left && !node->right) { // Check if there are no children
- (parent->left == node) ? (parent->left = NULL) : (parent->right = NULL);
- }else if(!node->left && node->right) { // check if there no left child for node "only right"
- (parent->left == node) ? (parent->left = node->right) : (parent->right=node->right);
- }else if(node->left && !node->right){ // check if there no right child for node "only left"
- (parent->left == node) ? (parent->left = node->left) : (parent->right=node->left );
- }else if(node->left && node->right){ // check if there both right and left children
- if(parent->right == node){ // Node is on right, we have to get smallest of right branch
- Node * smallest = getSmallest(node->right);
- printf("parent of smallest: [%d],smallest : [%d]\n", getParent(root,smallest)->data.id,smallest->data.id);
- }
- Node * smallest = getSmallest(node);
- Node * parentOfSmallest = getParent(root,smallest);
- if(parentOfSmallest->left == smallest)
- parentOfSmallest->left = NULL;
- else
- parentOfSmallest->right = NULL;
- if(parent->left==node) {
- parent->left = smallest;
- }else{
- parent->right = getSmallest(node->right);
- }
- smallest->left = node->left;
- smallest->right = node->right;
- }
- free(node);
- }else{
- // TRYING TO REACH THE NODE
- parent = root;
- if(node->data.id < root->data.id)
- root = root->left;
- else
- root = root->right;
- delete(root,parent,node);
- }
- }
- }
- */
- // END OF DELETING FROM BST FUNCTION.
- // START OF FUNCTION GETTING MAX,MIN VALUE IN A TREE.
- Node * getMax(Tree *root){
- return !root->right ? root : getMax(root->right);
- }
- Node * getMin(Tree *root){
- return !root->left ? root : getMax(root->left);
- }
- // END OF FUNCTION GETTING MAX,MIN VALUE IN A TREE.
- int data(Node *node){
- return node->data.id;
- }
- int hasChild(Node *node){
- return node->right || node->left;
- }
- void delete(Tree ** root, Node * parent, Node * node){
- if(!parent) {
- if(!node->left && !node->right){
- (*root)->data.id = ~(1<<31);
- }else if(!node->left && node->right){
- Node *minNode = getMin((*root)->right); Node *parentMinNode = getParent((*root),minNode);
- (parentMinNode->left == minNode) ? (parentMinNode->left = NULL) : (parentMinNode->right = NULL);
- minNode->left = (*root)->left; minNode->right = (*root)->right;
- (*root) = minNode;
- } else if(node->left && !node->right){
- Node *maxNode = getMax((*root)->left); Node * parentMaxNode = getParent((*root),maxNode);
- (parentMaxNode->left == maxNode) ? (parentMaxNode->left = NULL) : (parentMaxNode->right = NULL);
- maxNode->left = (*root)->left; maxNode->right = (*root)->right;
- (*root) = maxNode;
- } else if(node->left && node->right){
- Node *maxNode = getMax((*root)->left); Node * parentMaxNode = getParent((*root),maxNode);
- (parentMaxNode->left == maxNode) ? (parentMaxNode->left = NULL) : (parentMaxNode->right = NULL);
- maxNode->left = (*root)->left; maxNode->right = (*root)->right;
- (*root) = maxNode;
- }
- return ;
- }else if(parent){
- if(!node->left && !node->right){ // Not a single child
- (parent->left == node) ? (parent->left = NULL) : (parent->right = NULL) ;
- }else if(!node->left && node->right){ // only RIGHT child
- (parent->left == node) ? (parent->left = node->right) : (parent->right = node->right) ;
- }else if(node->left && !node->right){ // only LEFT child
- (parent->left == node) ? (parent->left = node->left) : (parent->right = node->right) ;
- }else if(node->left && node->right){ // have BOTH children
- Node *maxNode = getMax(node->left); Node *parentMaxNode = getParent((*root),maxNode);
- (parentMaxNode->left == maxNode )? (parentMaxNode->left = NULL) : (parentMaxNode->right = NULL);
- (parent->left == node) ? (parent->left = maxNode) : (parent->right = maxNode);
- maxNode->left = node->left; maxNode->right = node->right;
- }
- free(node);
- }
- }
- void build(Tree *root){
- insert(root,100);
- insert(root,70);
- insert(root,50);
- insert(root,76);
- insert(root,90);
- insert(root,200);
- insert(root,40);
- insert(root,60);
- insert(root,73);
- insert(root,77);
- insert(root,95);
- insert(root,150);
- insert(root,72);
- insert(root,74);
- }
- void buildMohab(Tree *root){
- insert(root,40);
- insert(root,90);
- insert(root,30);
- insert(root,45);
- insert(root,80);
- insert(root,100);
- insert(root,20);
- insert(root,41);
- insert(root,49);
- insert(root,200);
- }
- int main(){
- system("clear");
- printf("[NUMBER VALUE]::[ADDRESS OF NODE]\n");
- printf("\n====================================================\n");
- Tree *root = newNode(80);
- // Tree *root = newNode(50);
- /*Tree *node1 = addLeft(root,2);
- Tree *node2 = addRight(root,10);
- addLeft(node1,1);
- addRight(addRight(node1,4),5);
- addLeft(node2,9);
- addRight(addLeft(addRight(node2,100),50),60);*/
- // preTravers(root);
- // postTravers(root);
- // inTravers(root);
- // inShow(root,0);
- build(root);
- // insert(root,50);
- // insert(root,90);
- // insert(root,60);
- // insert(root,100);
- // insert(root,200);
- inShow(root,0);
- printf("\n====================================================\n");
- Node *node = search(root,80);
- delete(&root,getParent(root,node),node);
- inShow(root,0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement