fork(2) download
copy 
  1. // Author :: Gaurav Ahirwar
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct node 
  6. {	
  7.     int data;
  8.     struct node* left, *right;
  9. };
  10. typedef struct node* Node;
  11. typedef struct node node;
  12.  
  13. void inorder(Node root) {
  14. 	if(!root) return;
  15. 	inorder(root->left);
  16. 	cout << root->data << " ";
  17. 	inorder(root->right);
  18. }
  19.  
  20. Node newNode(int data)
  21. {
  22.     Node temp = (Node)malloc(sizeof(struct node));
  23.     temp->data  = data;
  24.     temp->left  = temp->right = NULL;
  25.     return(temp);
  26. }
  27.  
  28. void printlist(Node head) {
  29. 	if(!head) {
  30. 		cout << "Empty List\n";
  31. 		return;
  32. 	}
  33. 	while(head != NULL) {
  34. 		cout << head->data << " ";
  35. //		if(head->next) cout << "-> ";
  36. 		head = head->right;
  37. 	}
  38. 	cout << endl;
  39. }
  40. /*function of convert binary tree to DLL */
  41. void doubly(node *root, node **prev, node **head) {
  42. 	if(!root) return;
  43.  
  44. 	doubly(root->left, prev, head);
  45.  
  46. 	if(!(*prev)) *head = root;/* if prev null set head */
  47. 	root->left = *prev;	/*update left pointer */
  48. 	*prev = root;		/*Update prev for next call*/
  49.  
  50. 	doubly(root->right, prev, head);
  51. }
  52.  
  53. /*Wrapper for converting binary tree to DLL*/
  54. void convert(node **root) {
  55. 	Node prev = NULL;
  56. 	Node head;
  57.  
  58. 	doubly(*root, &prev, &head);
  59. 	/*update right pointers of all node in the list*/
  60. 	while(prev->left) {
  61. 		prev->left->right = prev;
  62. 		prev = prev->left;
  63. 	}
  64. 	*root = head; /* update root as head of DLL */
  65. }
  66.  
  67. /*function to print two sorted DLL in combined sorted form*/ 
  68. void printmerged(Node root1, Node root2) {
  69. 	while(root1 && root2) {
  70. 		if(root1->data < root2->data) {
  71. 			cout << root1->data << " ";
  72. 			root1 = root1->right;
  73. 		}
  74. 		else {
  75. 			cout << root2->data << " ";
  76. 			root2 = root2->right;
  77. 		}
  78. 	}
  79.  
  80. 	while(root1) {
  81. 		cout << root1->data << " ";
  82. 		root1 = root1->right;
  83. 	}
  84. 	while(root2) {
  85. 		cout << root2->data << " ";
  86. 		root2 = root2->right;
  87. 	}
  88. 	cout << endl;
  89. }
  90.  
  91. int main() {
  92.  
  93. // Let us construct the BST shown in the above figure
  94.     node *root2  	   = newNode(4);
  95.     root2->left        = newNode(2);
  96.     root2->right       = newNode(6);
  97.     root2->left->left  = newNode(1);
  98.     root2->left->right = newNode(3);
  99.     root2->right->left  = newNode(5);
  100.     root2->right->right = newNode(7);
  101.  	/* Constructed binary tree is 
  102.             4
  103.           /   \
  104.         2      6
  105.       /  \	  /	\
  106.     1     3  5  7
  107.   
  108.   */
  109.  
  110.   	node *root1  	  = newNode(100);
  111.     root1->left        = newNode(90);
  112.     root1->right       = newNode(105);
  113.     root1->left->left  = newNode(70);
  114.     root1->left->right = newNode(95);
  115.     root1->right->left  = newNode(103);
  116.     root1->right->right = newNode(106);
  117.  
  118.     /* Constructed binary tree is 
  119.      
  120. 	        100
  121.           /   \
  122.         90      105
  123.       /  \	  /	  \
  124.     70   95  103  106
  125.   
  126.   */
  127.  
  128. 	convert(&root1);
  129. 	convert(&root2);
  130. 	printmerged(root1, root2);
  131.   	return 0;
  132. }
Success #stdin #stdout 0s 3232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 4 5 6 7 70 90 95 100 103 105 106
https://ideone.com/kTexal
language:
C++14 (gcc 8.3)
created:
8 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!