Advertisement
tariq_zaghal

BST

Jun 1st, 2023 (edited)
1,421
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.50 KB | Source Code | 0 0
  1. //Implemented by: Tariq Zaghal
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <math.h>
  5.  
  6.  
  7. typedef struct BstNode* TNode;
  8.  
  9. struct BstNode{
  10.     int data;
  11.     TNode left;
  12.     TNode right;
  13.     int count;
  14. };
  15.  
  16.  
  17. TNode makeEmpty(TNode root);
  18. TNode find(int x, TNode root);
  19. TNode findMin(TNode root);
  20. TNode findMax(TNode root);
  21. TNode insert(int data, TNode root);
  22. TNode delete(int x, TNode T);
  23. int findHeight(TNode root);
  24. int max(int x, int y);
  25. void trace(TNode T);
  26. struct BstNode* getNewNode(int data);
  27.  
  28. int main(){
  29.     TNode root = NULL;
  30.  
  31.     root = insert(13,root);
  32.     root = insert(3,root);
  33.     root = insert(7,root);
  34.     root = insert(20,root);
  35.     root = insert(8,root);
  36.     root = delete(5,root);
  37.     trace(root);
  38.  
  39.     return 0;
  40. }
  41.  
  42.  
  43. void trace(TNode T){
  44.     if(T!=NULL){
  45.         trace(T->left);
  46.         printf("%d\n ",T->data);
  47.         trace(T->right);
  48.     }
  49.  
  50. }
  51.  
  52. int findHeight(TNode root){
  53.  
  54.     if(root == NULL)
  55.         return -1;
  56.     else
  57.         return max(findHeight(root->left),findHeight(root->left))+1;
  58. }
  59.  
  60.  
  61.  
  62. int max(int x, int y){
  63.     if(x>=y)
  64.         return x;
  65.     else
  66.         return y;
  67. }
  68.  
  69.  
  70. TNode makeEmpty(TNode root){
  71.     if(root!=NULL){
  72.         return makeEmpty(root->left);
  73.         return makeEmpty(root->right);
  74.         free(root);
  75.     }
  76.  
  77.     return NULL;
  78. }
  79.  
  80.  
  81. TNode find(int x, TNode root){
  82.     if(root == NULL)
  83.         return NULL;
  84.     if(root->data == x){
  85.         return root;
  86.     }else if(x<root->data){
  87.         return find(x,root->left);
  88.     }else{
  89.         return find(x,root->right);
  90.     }
  91. }
  92.  
  93.  
  94. TNode findMin(TNode root){
  95.     if(root == NULL)
  96.         return NULL;
  97.     else if (root->left == NULL)
  98.         return root;
  99.     else
  100.         return findMin(root->left);
  101. }
  102.  
  103.  
  104.  
  105. TNode findMax(TNode root){
  106.     if(root == NULL)
  107.         return NULL;
  108.     else if (root->right == NULL)
  109.         return root;
  110.     else
  111.         return findMax(root->right);
  112. }
  113.  
  114.  
  115.  
  116.  
  117.  
  118. TNode delete(int x, TNode T){
  119.     TNode temp;
  120.     if(T==NULL){
  121.         printf("Didn't find the node to be deleted!\n");
  122.         return NULL;
  123.     }
  124.     else if (x<T->data) T->left = delete(x,T->left);
  125.     else if (x>T->data) T->right = delete(x,T->right);
  126.  
  127.     else{//element Found!!
  128.  
  129.        
  130.  
  131.  
  132.         if(T->left == NULL && T->right == NULL){//No children
  133.             free(T);
  134.             T = NULL;
  135.         }else if(T->left == NULL){  //one right child
  136.             TNode temp = T;
  137.             T = T->right;
  138.             free(temp);
  139.         }else if(T->right == NULL){ //one left child
  140.             TNode temp = T;
  141.             T = T->left;
  142.             free(temp);
  143.         }else{  //two children
  144.             TNode temp = findMin(T->right);
  145.             T->data = temp->data;
  146.             delete(T->data, T->right);
  147.         }
  148.  
  149.  
  150.        
  151.     }
  152.  
  153.     return T;
  154.  
  155.    
  156. }
  157.  
  158.  
  159.  
  160.  
  161. struct BstNode* getNewNode(int data){
  162.     struct BstNode* newNode = malloc(sizeof(struct BstNode));
  163.  
  164.     newNode->data = data;
  165.     newNode->left = NULL;
  166.     newNode->right = NULL;
  167.     newNode->count = 1;
  168.  
  169.     return newNode;
  170. }
  171.  
  172.  
  173. struct BstNode* insert (int data, TNode root){
  174.     if(root == NULL ){//the tree is empty
  175.         root = getNewNode(data);
  176.        // printf("%d\n",root->data);
  177.         return root;
  178.     }else if(data == root->data){
  179.         //printf("%d\n",root->data);
  180.         root->count++;
  181.     }else if (data<root->data)
  182.     {
  183.         root->left = insert(data , root->left);
  184.     }else{
  185.         root->right = insert(data , root->right);
  186.     }
  187.        
  188. }
  189.  
  190.  
  191.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement