fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <stdbool.h>
  5.  
  6. struct node {
  7.    int data;   
  8.    struct node *leftChild;
  9.    struct node *rightChild;
  10. };
  11. struct node *root = NULL;
  12. void insert(int data){
  13.    struct node *tempNode = (struct node*) malloc(sizeof(struct node));
  14.    struct node *current;
  15.    struct node *parent;
  16.  
  17.    tempNode->data = data;
  18.    tempNode->leftChild = NULL;
  19.    tempNode->rightChild = NULL;
  20.  
  21.    //if tree is empty
  22.    if(root == NULL){
  23.       root = tempNode;
  24.    } else {
  25.       current = root;
  26.       parent = NULL;
  27.       while(1){                
  28.          parent = current;
  29.          //go to left of the tree
  30.          if(data < parent->data){
  31.             current = current->leftChild;                
  32.             //insert to the left
  33.             if(current == NULL){
  34.                parent->leftChild = tempNode;
  35.                return;
  36.             }
  37.          }//go to right of the tree
  38.          else{
  39.             current = current->rightChild;
  40.             //insert to the right
  41.             if(current == NULL){
  42.                parent->rightChild = tempNode;
  43.                return;
  44.             }
  45.          }
  46.       }       
  47.    }
  48. }
  49. struct node* search(int data){
  50.    struct node *current = root;
  51.    printf("Visiting elements: ");
  52.    while(current->data != data){
  53.       if(current != NULL)
  54.          printf("%d ",current->data); 
  55.          //go to left tree
  56.          if(current->data > data){
  57.             current = current->leftChild;
  58.          }//else go to right tree
  59.          else{                
  60.             current = current->rightChild;
  61.          }
  62.          //not found
  63.          if(current == NULL){
  64.             return NULL;
  65.          }
  66.       }
  67.    return current;
  68. }
  69. void preOrder(struct node* root){
  70.    if(root!=NULL){
  71.       printf("%d ",root->data);
  72.       preOrder(root->leftChild);
  73.       preOrder(root->rightChild);
  74.    }
  75. }
  76. void inOrder(struct node* root){
  77.    if(root!=NULL){
  78.       inOrder(root->leftChild);
  79.       printf("%d ",root->data);          
  80.       inOrder(root->rightChild);
  81.    }
  82. }
  83. void postOrder(struct node* root){
  84.    if(root!=NULL){            
  85.       postOrder(root->leftChild);
  86.       postOrder(root->rightChild);
  87.       printf("%d ",root->data);
  88.    }
  89. }
  90. void traverse(int traversalType){
  91.    switch(traversalType){
  92.       case 1:
  93.          printf("\nPreorder traversal: ");
  94.          preOrder(root);
  95.          break;
  96.       case 2:
  97.          printf("\nInorder traversal: ");
  98.          inOrder(root);
  99.          break;
  100.       case 3:
  101.          printf("\nPostorder traversal: ");
  102.          postOrder(root);
  103.          break;
  104.    }            
  105. }  
  106.  
  107. int main()
  108. {
  109.    /*                     11               //Level 0
  110.    */
  111.    insert(11);
  112.    /*                     11               //Level 0
  113.    *                      |
  114.    *                      |---20           //Level 1
  115.    */
  116.    insert(20);
  117.    /*                     11               //Level 0
  118.    *                      |
  119.    *                  3---|---20           //Level 1
  120.    */
  121.    insert(3);        
  122.    /*                     11               //Level 0
  123.    *                      |
  124.    *                  3---|---20           //Level 1
  125.    *                           |
  126.    *                           |--42       //Level 2
  127.    */
  128.    insert(42);
  129.    /*                     11               //Level 0
  130.    *                      |
  131.    *                  3---|---20           //Level 1
  132.    *                           |
  133.    *                           |--42       //Level 2
  134.    *                               |
  135.    *                               |--54   //Level 3
  136.    */
  137.    insert(54);
  138.    /*                     11               //Level 0
  139.    *                      |
  140.    *                  3---|---20           //Level 1
  141.    *                           |
  142.    *                       16--|--42       //Level 2
  143.    *                               |
  144.    *                               |--54   //Level 3
  145.    */
  146.    insert(16);
  147.    /*                     11               //Level 0
  148.    *                      |
  149.    *                  3---|---20           //Level 1
  150.    *                           |
  151.    *                       16--|--42       //Level 2
  152.    *                               |
  153.    *                           32--|--54   //Level 3
  154.    */
  155.    insert(32);
  156.    /*                     11               //Level 0
  157.    *                      |
  158.    *                  3---|---20           //Level 1
  159.    *                  |        |
  160.    *                  |--9 16--|--42       //Level 2
  161.    *                               |
  162.    *                           32--|--54   //Level 3
  163.    */
  164.    insert(9);
  165.    /*                     11               //Level 0
  166.    *                      |
  167.    *                  3---|---20           //Level 1
  168.    *                  |        |
  169.    *                  |--9 16--|--42       //Level 2
  170.    *                     |         |
  171.    *                  4--|     32--|--54   //Level 3
  172.    */
  173.    insert(4);
  174.    /*                     11               //Level 0
  175.    *                      |
  176.    *                  3---|---20           //Level 1
  177.    *                  |        |
  178.    *                  |--9 16--|--42       //Level 2
  179.    *                     |         |
  180.    *                  4--|--10 32--|--54   //Level 3
  181.    */
  182.    insert(10);
  183.  
  184.    struct node * temp = search(32);
  185.    if(temp!=NULL){
  186.       printf("Element found.\n");
  187.       printf("( %d )",temp->data);
  188.       printf("\n");
  189.    } else {
  190.       printf("Element not found.\n");
  191.    }
  192.  
  193.    struct node *node1 = search(2);
  194.    if(node1!=NULL){
  195.       printf("Element found.\n");
  196.       printf("( %d )",node1->data);
  197.       printf("\n");
  198.    } else {
  199.       printf("Element not found.\n");
  200.    }        
  201.  
  202.    //pre-order traversal
  203.    //root, left ,right
  204.    traverse(1);
  205.    //in-order traversal
  206.    //left, root ,right
  207.    traverse(2);
  208.    //post order traversal
  209.    //left, right, root
  210.    traverse(3);       
  211. }
Success #stdin #stdout 0s 5516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Visiting elements: 11 20 42 Element found.
( 32 )
Visiting elements: 11 3 Element not found.

Preorder traversal: 11 3 9 4 10 20 16 42 32 54 
Inorder traversal: 3 4 9 10 11 16 20 32 42 54 
Postorder traversal: 4 10 9 3 16 32 54 42 20 11
https://ideone.com/g2XMKT
language:
C (gcc 8.3)
created:
1 year 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!