fork download 
  1. /* 
  2.  * File:   morrisinorder.c
  3.  * Author: srkrishnan
  4.  *
  5.  * Created on July 5, 2011, 7:28 AM
  6.  */
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10.  
  11. typedef struct Tnode {
  12.     int data;
  13.     struct Tnode *left;
  14.     struct Tnode *right;
  15.     struct Tnode *next;
  16. } Tnode;
  17.  
  18. Tnode* createnode(int data) {
  19.     Tnode *n = (Tnode*) malloc(sizeof (Tnode));
  20.     n->left = n->right =n->next= NULL;
  21.     n->data = data;
  22.     return n;
  23. }
  24.  
  25. inordermorrisiterative(Tnode *root) {
  26.     Tnode *current = root, *pred = NULL, *succesor = NULL;
  27.  
  28.     while (current != NULL) {
  29.         succesor = current->right;
  30.         if (succesor != NULL && current->next==NULL) {
  31.             while (succesor->left != NULL) {
  32.                 succesor = succesor->left;
  33.             }
  34.             current->next = succesor;
  35.         }
  36.         if (current->left == NULL) {
  37.             printf(" %d ", current->data);
  38.             current = current->right;
  39.         } else {
  40.             pred = current->left;
  41.             while (pred->right != NULL && pred->right != current) {
  42.                 pred = pred->right;
  43.             }
  44.  
  45.             if (pred->right == NULL) {
  46.                 pred->next = current;
  47.                 pred->right = current;
  48.                 current = current->left;
  49.             } else {
  50.                 pred->right = NULL;
  51.                 printf(" %d ", current->data);
  52.                 current = current->right;
  53.             }
  54.         }
  55.     }
  56. }
  57.  
  58. void printinorder(Tnode *root) {
  59.  
  60.     while(root->left!=NULL)
  61.         root=root->left;
  62.  
  63.     while (root!= NULL) {
  64.         printf(" %d ", root->data);
  65.         root = root->next;
  66.     }
  67. }
  68.  
  69. int main(int argc, char** argv) {
  70.  
  71.     Tnode *root;
  72.  
  73.     root = createnode(15);
  74.  
  75.     root->left = createnode(7);
  76.     root->right = createnode(25);
  77.  
  78.     root->left->left = createnode(3);
  79.     root->left->right = createnode(10);
  80.  
  81.     root->right->left = NULL;
  82.     root->right->right = createnode(50);
  83.  
  84.     root->left->right->left = createnode(8);
  85.     root->left->right->right = createnode(12);
  86.  
  87.     root->left->right->left->left = NULL;
  88.     root->left->right->left->right = createnode(9);
  89.  
  90.     root->left->right->right->left = createnode(11);
  91.     root->left->right->right->right = createnode(14);
  92.  
  93.     root->right->right->left = createnode(30);
  94.     root->right->right->right = createnode(55);
  95.  
  96.     root->right->right->right->left = createnode(52);
  97.     root->right->right->right->right = NULL;
  98.  
  99.     inordermorrisiterative(root);
  100.     printf("\n");
  101.     printinorder(root);
  102.  
  103.     return (EXIT_SUCCESS);
  104. }
  105.  
Success #stdin #stdout 0.01s 6352KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/qYKMW
language:
Python (cpython 2.7.16)
created:
14 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!