fork download
copy 
  1. /* 
  2.  * File:   BTMirrorIterative.c
  3.  * Author: srkrishnan
  4.  *
  5.  * Created on June 30, 2011, 2:18 PM
  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. } Tnode;
  16.  
  17. typedef struct List {
  18.     Tnode *data;
  19.     struct List *link;
  20. } List;
  21.  
  22. List *head = NULL;
  23.  
  24. List* createlistnode() {
  25.     List *n = (List*) malloc(sizeof (List));
  26.     n->data = NULL;
  27.     n->link = NULL;
  28.     return n;
  29. }
  30.  
  31. Tnode* createnode(int data) {
  32.     Tnode *n = (Tnode*) malloc(sizeof (Tnode));
  33.     n->left = n->right = NULL;
  34.     n->data = data;
  35.     return n;
  36. }
  37.  
  38. void push(Tnode *root) {
  39.     List *tmp = NULL;
  40.     if (head == NULL) {
  41.         head = createlistnode();
  42.         head->data = root;
  43.         return;
  44.     }
  45.     tmp = createlistnode();
  46.     tmp->data = root;
  47.     tmp->link = head;
  48.     head = tmp;
  49. }
  50.  
  51. Tnode* pop() {
  52.     List *tmp = NULL;
  53.     Tnode *t=NULL;
  54.     if (head != NULL) {
  55.         tmp = head;
  56.         head = head->link;
  57.         t=tmp->data;
  58.         free(tmp);
  59.     }
  60.     return t;
  61. }
  62.  
  63. Tnode *BTMirrorIterative(Tnode *root) {
  64.     Tnode *node = NULL, *tmp = NULL;
  65.  
  66.     if (root == NULL)
  67.         return root;
  68.     while (root) {
  69.         push(root);
  70.         if (root->left != NULL)
  71.             root = root->left;
  72.         else if (root->right != NULL)
  73.             root = root->right;
  74.         else {
  75.             do {
  76.                 node = pop();
  77.                 tmp = node->left;
  78.                 node->left = node->right;
  79.                 node->right = tmp;
  80.  
  81.                 if (head == NULL)
  82.                     return root;
  83.                 root = head->data;
  84.             } while (root->right == node || root->right == NULL);
  85.             if (root->right != NULL)
  86.                 root = root->right;
  87.         }
  88.     }
  89.     return NULL;
  90. }
  91.  
  92. void inorder(Tnode *root) {
  93.     if (root == NULL)
  94.         return;
  95.     inorder(root->left);
  96.     printf(" %d ", root->data);
  97.     inorder(root->right);
  98. }
  99.  
  100. int isempty() {
  101.     if (head == NULL)
  102.         return 1;
  103.     return 0;
  104. }
  105.  
  106. int main(int argc, char** argv) {
  107.  
  108.     Tnode *root;
  109.  
  110.     root = createnode(15);
  111.  
  112.     root->left = createnode(7);
  113.     root->right = createnode(25);
  114.  
  115.     root->left->left = createnode(3);
  116.     root->left->right = createnode(10);
  117.  
  118.     root->right->left = NULL;
  119.     root->right->right = createnode(50);
  120.  
  121.     root->left->right->left = createnode(8);
  122.     root->left->right->right = createnode(12);
  123.  
  124.     root->left->right->left->left = NULL;
  125.     root->left->right->left->right = createnode(9);
  126.  
  127.     root->left->right->right->left = createnode(11);
  128.     root->left->right->right->right = createnode(14);
  129.  
  130.     root->right->right->left = createnode(30);
  131.     root->right->right->right = createnode(55);
  132.  
  133.     root->right->right->right->left = createnode(52);
  134.     root->right->right->right->right = NULL;
  135.     inorder(root);
  136.     printf("\nGenerating Mirror....\n");
  137.     root = BTMirrorIterative(root);
  138.     inorder(root);
  139.  
  140.     return (EXIT_SUCCESS);
  141. }
  142.  
Success #stdin #stdout 0s 1852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 3  7  8  9  10  11  12  14  15  25  30  50  52  55 
Generating Mirror....
 55  52  50  30  25  15  14  12  11  10  9  8  7  3
https://ideone.com/yufa2
language:
C (gcc 8.3)
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!