fork(4) download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. /* A binary tree tNode has data, pointer to left child
  7.    and a pointer to right child */
  8. struct tNode
  9. {
  10.    int data;
  11.    struct tNode* left;
  12.    struct tNode* right;
  13. };
  14.  
  15. struct tNode* findBSTMin(struct tNode *root) {
  16. 	if(!root) { return root;}
  17. 	while(root->left) {
  18. 		root = root->left;
  19. 	}
  20. 	return root;
  21. }
  22.  
  23. struct tNode* successorBST(struct tNode *curr, struct tNode *root) {
  24. 	if(!curr) { return curr;}
  25. 	if(curr->right) {
  26. 		return findBSTMin(curr->right);
  27. 	} 
  28. 	struct tNode* successor = 0;
  29. 	while(root && root != curr) {
  30. 		if(curr->data < root->data) {
  31. 			successor = root;
  32. 			root = root->left;
  33. 		} else {
  34. 			root = root->right;
  35. 		}
  36. 	}
  37. 	return successor;
  38. }
  39.  
  40.  
  41. void InOrderIteravtiveNoStack(struct tNode *root) {
  42. 	if(!root) { return; }
  43. 	struct tNode *curr = findBSTMin(root);
  44. 	while(curr) {
  45. 		cout << curr->data << " ";
  46. 		curr = successorBST(curr, root);
  47. 	}
  48. 	return;
  49. }
  50.  
  51. /* Function to traverse binary tree without recursion and 
  52.    without stack */
  53. void MorrisTraversal(struct tNode *root)
  54. {
  55.   struct tNode *current,*pre;
  56.  
  57.   if(root == NULL)
  58.      return; 
  59.  
  60.   current = root;
  61.   while(current != NULL)
  62.   {                 
  63.     if(current->left == NULL)
  64.     {
  65.       printf(" %d ", current->data);
  66.       current = current->right;      
  67.     }    
  68.     else
  69.     {
  70.       /* Find the inorder predecessor of current */
  71.       pre = current->left;
  72.       while(pre->right != NULL && pre->right != current)
  73.         pre = pre->right;
  74.  
  75.       /* Make current as right child of its inorder predecessor */
  76.       if(pre->right == NULL)
  77.       {
  78.         pre->right = current;
  79.         current = current->left;
  80.       }
  81.  
  82.       /* Revert the changes made in if part to restore the original 
  83.         tree i.e., fix the right child of predecssor */   
  84.       else 
  85.       {
  86.         pre->right = NULL;
  87.         printf(" %d ",current->data);
  88.         current = current->right;      
  89.       } /* End of if condition pre->right == NULL */
  90.     } /* End of if condition current->left == NULL*/
  91.   } /* End of while */
  92. }
  93.  
  94. /* UTILITY FUNCTIONS */
  95. /* Helper function that allocates a new tNode with the
  96.    given data and NULL left and right pointers. */
  97. struct tNode* newtNode(int data)
  98. {
  99.   struct tNode* tNode = (struct tNode*)
  100.                        malloc(sizeof(struct tNode));
  101.   tNode->data = data;
  102.   tNode->left = NULL;
  103.   tNode->right = NULL;
  104.  
  105.   return(tNode);
  106. }
  107.  
  108. /* Driver program to test above functions*/
  109. int main()
  110. {
  111.  
  112.   /* Constructed binary tree is
  113.             5
  114.           /   \
  115.         2      6
  116.       /  \
  117.     1     4
  118.   */
  119.   struct tNode *root = newtNode(5);
  120.   root->left        = newtNode(2);
  121.   root->right       = newtNode(6);
  122.   root->left->left  = newtNode(1);
  123.   root->left->right = newtNode(4); 
  124.  
  125.   //MorrisTraversal(root);
  126.  
  127.   InOrderIteravtiveNoStack(root);
  128.  
  129.   getchar();
  130.   return 0;
  131. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 4 5 6
https://ideone.com/qqd2PJ
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

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!