fork download
copy 
  1. #include <stdio.h>
  2. #include <malloc.h>
  3.  
  4. //BST = Binary Search Tree ( insert, search, traversals: inorder, preorder, postorder, remove)
  5. //arbore binar de cautare
  6.  
  7. //strtok token
  8.  
  9. typedef struct Node {
  10.  
  11.        int data;
  12.        struct Node *left;
  13.        struct Node *right;
  14.  
  15. } Node;
  16.  
  17. Node *insert(Node *root, int val) {
  18.  
  19.      if(root == NULL) {
  20.  
  21.          //root = new Node;aloca spatiu in HEAP pentru Node
  22.          root = (Node*)malloc(sizeof(Node));
  23.          root->data = val;
  24.          root->left = NULL; //0, nullptr
  25.          root->right = NULL; //
  26.  
  27.      } else {
  28.  
  29.         if( root->data < val ) {
  30.  
  31.             root->right = insert(root->right, val);
  32.  
  33.         } else {
  34.  
  35.             root->left = insert(root->left, val);
  36.         }
  37.  
  38.      }
  39.  
  40.      return root;
  41. }
  42.  
  43. void inorder(Node *node) {
  44.  
  45.      if(node) {
  46.        inorder(node->left);
  47.        printf("%d ", node->data);
  48.        inorder(node->right);
  49.      }
  50. }
  51.  
  52. void preorder(Node *node) {
  53.  
  54.   if(node) {
  55.     printf("%d ", node->data);
  56.     preorder(node->left);
  57.     preorder(node->right);
  58.   }
  59. }
  60.  
  61. void postorder(Node *node) {
  62.  
  63.   if(node) {
  64.     printf("%d ", node->data);
  65.     postorder(node->left);
  66.     postorder(node->right);
  67.   }
  68. }
  69.  
  70. int search(Node *root, int key) {
  71.  
  72.     if(root == NULL) {
  73.  
  74.        return 0;
  75.  
  76.     } else if( root->data > key ) {
  77.  
  78.        return search(root->left, key);
  79.  
  80.     } else if(root->data < key ) {
  81.  
  82.        return search(root->right, key);
  83.  
  84.     } else {
  85.  
  86.       return 1;
  87.     }
  88.  
  89. }
  90.  
  91. //                  subarborele drept
  92. Node *mostlyLeft(Node *root) {
  93.  
  94.       while( root->left ) root = root->left;
  95.  
  96.       return root;
  97. }
  98.  
  99.  
  100. //stergerea: se sterge nodul si se inlocuieste cu cel mai din stanga nod din subarborele drept
  101. Node* remove(Node *root, int key) {
  102.  
  103.       if(root == NULL) {
  104.  
  105.          return root;
  106.  
  107.       } else if(root->data  > key ) {
  108.  
  109.           root->left = remove(root->left, key);
  110.  
  111.       } else if(root->data < key ) {
  112.  
  113.           root->right = remove(root->right, key);
  114.  
  115.       } else {
  116.  
  117.           if(root->left == NULL && root->right == NULL) {
  118.  
  119.               free( root );
  120.               return NULL;
  121.  
  122.           } else if( root->left == NULL) {
  123.  
  124.             Node *temp = root->right;
  125.             free(root);
  126.             return temp;
  127.  
  128.           } else if( root->right == NULL)  {
  129.  
  130.             Node *temp = root->left;
  131.             free(root);
  132.             return temp;
  133.  
  134.           } else if( root->left != NULL && root->right != NULL ) {
  135.  
  136.             //cel mai din stanga din subarborele drept
  137.              Node *temp = mostlyLeft( root->right );
  138.  
  139.              root->data  = temp->data;
  140.  
  141.  
  142.              root->right = remove(root->right, temp->data);
  143.           }
  144.       }
  145.  
  146.       return root;
  147. }
  148.  
  149. int main(int argc, char const *argv[]) {
  150.  
  151.   Node *root = NULL;
  152.  
  153.   root = insert(root, 12);
  154.  
  155.   insert(root, 5);
  156.   insert(root, 4);
  157.   insert(root, 18);
  158.   insert(root, 52);
  159.   insert(root, 22);
  160.   insert(root, 51);
  161.   insert(root, 53);
  162.  
  163.   printf("\nInorder: \n");
  164.   inorder( root );
  165.  
  166.   printf("\nPreorder: \n");
  167.   preorder( root );
  168.  
  169.   printf("\nPostorder: \n");
  170.   postorder( root );
  171.  
  172.   int key_search = 18;
  173.  
  174.   int answer;
  175.  
  176.   answer = search( root, key_search );
  177.  
  178.   if( answer == 1 ) {
  179.     printf("\nThe key: %d Found in BST\n", key_search);
  180.   } else {
  181.     printf("\nThe key: %d Not Found in BST\n", key_search);
  182.   }
  183.  
  184.   int key_remove = 52;
  185.  
  186.   if(search(root, key_remove) == 1) {
  187.      printf("\n%s: %d\n", "Stergere Node", key_remove);
  188.      remove(root, key_remove);
  189.      inorder(root);
  190.   } else {
  191.      printf("\n%s: %d\n", "Nu am cum sa-l sterg pentru ca nu exista in BST", key_remove);
  192.   }
  193.  
  194.   //free -> elibereaza spatiul de memorie din HEAP
  195.   //malloc - se aloca spatiu in HEAP
  196.   return 0;
  197. }
  198.  
Success #stdin #stdout 0s 5280KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Inorder: 
4 5 12 18 22 51 52 53 
Preorder: 
12 5 4 18 52 22 51 53 
Postorder: 
12 5 4 18 52 22 51 53 
The key: 18 Found in BST

Stergere Node: 52
4 5 12 18 22 51 53
https://ideone.com/PNPt2p
BST recursive
language:
C++ (gcc 8.3)
created:
330 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!