fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <limits.h>
  4.  
  5.  
  6. int totalElem = 8;
  7.  
  8. typedef struct BST {
  9.     int data;
  10.     struct BST *left;
  11.     struct BST *right;
  12. } nodeBST;
  13.  
  14. nodeBST* addNode(int data);
  15. void addNodeToBST(nodeBST *root, nodeBST *node);
  16. void traverse(nodeBST *root);
  17. void createBST(int arr[]);
  18. void iterativeInorder(nodeBST *root);
  19.  
  20. int main()
  21. {
  22.     int arr[10] = {20,9,5,15,4,6,30,35};
  23.  
  24.     createBST(arr);
  25.  
  26.     return 0;
  27. }
  28.  
  29. void MorrisInorder(nodeBST *root) {
  30.     nodeBST* current,*pre;
  31.     current=root;
  32.     while(current!=NULL) {
  33.         if(current->left==NULL) {
  34.             printf("%d ",current->data);
  35.             current=current->right;
  36.         }
  37.         else {
  38.             pre=current->left;
  39.             while(pre->right != NULL && pre->right !=current)
  40.                 pre=pre->right;
  41.             if(pre->right==NULL) {
  42.                 printf("Link %d, %d\n", pre->data, current->data);
  43.                 pre->right=current;
  44.                 current=current->left;
  45.             }
  46.             else {
  47.                 pre->right=NULL;
  48.                 printf("%d ",current->data);
  49.                 current=current->right;
  50.             }
  51.         }
  52.     }
  53. }
  54.  
  55. // Recursive inorder traverse
  56. void traverse(nodeBST *root)
  57. {
  58.     if (root == NULL) {
  59.         return;
  60.     } else {
  61.         traverse(root->left);
  62.         printf("%d ", root->data);
  63.         traverse(root->right);
  64.     }
  65.  
  66.     return;
  67. }
  68.  
  69. void createBST(int arr[])
  70. {
  71.     nodeBST *node;
  72.     nodeBST *root;
  73.     int i = 0;
  74.  
  75.     for (i = 0; i < totalElem; i++) {
  76.         node = addNode(arr[i]);
  77.         if (node == NULL) {
  78.             return;
  79.         }
  80.  
  81.         if (i == 0) {
  82.             root = node;
  83.             continue;
  84.         }
  85.  
  86.         addNodeToBST(root, node);
  87.     }
  88.  
  89.     printf("Recursive Inorder:\n");
  90.     traverse(root);
  91.     printf("\n\nMorris Inorder:\n");
  92.     MorrisInorder(root);
  93.     printf("\n\nIterative Inorder:\n");
  94.     iterativeInorder(root);
  95. }
  96.  
  97. nodeBST* addNode(int data)
  98. {
  99.     nodeBST *node = (nodeBST*)calloc(1, sizeof(nodeBST));
  100.  
  101.     if (node == NULL) {
  102.         return NULL;
  103.     }
  104.  
  105.     node->data = data;
  106.     node->left = NULL;
  107.     node->right = NULL;
  108.  
  109.     return node;
  110. }
  111.  
  112. void addNodeToBST(nodeBST *root, nodeBST *node)
  113. {
  114.     while(root != NULL) {
  115.         if (node->data < root->data) {
  116.             if (root->left != NULL) {
  117.                 root = root->left;
  118.             } else {
  119.                 root->left = node;
  120.                 return;
  121.             }
  122.         } else {
  123.             if (root->right != NULL) {
  124.                 root = root->right;
  125.             } else {
  126.                 root->right = node;
  127.                 return;
  128.             }
  129.         }
  130.     }
  131.  
  132.     return;
  133. }
  134.  
  135. typedef struct stack {
  136.     nodeBST* node;
  137.     struct stack* next;
  138. } stackNode;
  139.  
  140. stackNode* head;
  141. stackNode* top;
  142.  
  143. void createStack()
  144. {
  145.     stackNode* root = (stackNode*)malloc(sizeof(stackNode));
  146.  
  147.     if (root == NULL) {
  148.         //ASSERT
  149.     }
  150.  
  151.     root->node = NULL;
  152.     root->next = NULL;
  153.  
  154.     head = root;
  155.     top = root;
  156. }
  157.  
  158. void push(nodeBST* treeNode)
  159. {
  160.     stackNode* temp = (stackNode*)malloc(sizeof(stackNode));
  161.     if (temp == NULL) {
  162.         //ASSERT
  163.     }
  164.  
  165.     temp->node = treeNode;
  166.     temp->next = head->next;
  167.     head->next = temp;
  168.  
  169.     top = head->next;
  170. }
  171.  
  172. int isStackEmpty()
  173. {
  174.     if (head->next == NULL) {
  175.         return 1;
  176.     }
  177.  
  178.     return 0;
  179. }
  180.  
  181. nodeBST* pop()
  182. {
  183.     stackNode* temp;
  184.  
  185.     if (!isStackEmpty()) {
  186.         temp = top;
  187.         head->next = top->next;
  188.  
  189.         if (head->next == NULL) {
  190.             top = head;
  191.         } else {
  192.             top = head->next;
  193.         }
  194.  
  195.         return temp->node;
  196.     }
  197.  
  198.     return head->node;
  199. }
  200.  
  201. // Iterative
  202. // 1) Create an empty stack S.
  203. // 2) Initialize current node as root
  204. // 3) Push the current node to S and set current = current->left until current is NULL
  205. // 4) If current is NULL and stack is not empty then 
  206. //      a) Pop the top item from stack.
  207. //      b) Print the popped item, set current = current->right
  208. //      c) Go to step 3.
  209. // 5) If current is NULL and stack is empty then we are done.
  210.  
  211. void iterativeInorder(nodeBST *root)
  212. {
  213.     createStack();
  214.  
  215.     while(1) {
  216.         if (root != NULL) {
  217.             // Keep pushing in the stack
  218.             push(root);
  219.             root = root->left;
  220.         } else {
  221.             if (isStackEmpty()) {
  222.                 break;
  223.             }
  224.  
  225.             root = pop();
  226.             printf("%d ", root->data);
  227.  
  228.             root = root->right;
  229.         }
  230.     }
  231. }
  232.  
Success #stdin #stdout 0s 2380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Recursive Inorder:
4 5 6 9 15 20 30 35 

Morris Inorder:
Link 15, 20
Link 6, 9
Link 4, 5
4 5 6 9 15 20 30 35 

Iterative Inorder:
4 5 6 9 15 20 30 35
https://ideone.com/Bo2ZpL
Tree in order traversal
language:
C (gcc 8.3)
created:
10 years 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!