fork(5) download
copy 
  1. #include<stdio.h>
  2. #include<malloc.h>
  3.  
  4. struct binaryTreeNode{
  5. 	int data;
  6. 	struct binaryTreeNode * left;
  7. 	struct binaryTreeNode * right;
  8. };
  9.  
  10. struct node
  11. {
  12. 	struct binaryTreeNode * data;
  13. 	struct node * next;
  14. };
  15.  
  16. struct queue
  17. {
  18. 	struct node * front;
  19. 	struct node * rear;
  20. };
  21.  
  22. struct queue * enQueue(struct queue * q, struct binaryTreeNode * num)
  23. {
  24. 	struct node * temp = (struct node*)malloc(sizeof(struct node));
  25. 	temp -> data = num;
  26. 	temp -> next = NULL;
  27. 	if(q == NULL)
  28. 	{
  29. 		q = (struct queue*)malloc(sizeof(struct queue));		
  30. 		q -> front = temp;
  31. 	}
  32. 	else
  33. 		q -> rear -> next = temp;
  34. 	q -> rear = temp;
  35. 	//Code obtained from http://w...content-available-to-author-only...s.com
  36. 	//Feel free to copy but please acknowledge the site wherever possible
  37. 	return q;
  38. }
  39.  
  40. struct queue * deQueue(struct queue * q)
  41. {
  42. 	struct node * temp = q->front;
  43. 	q -> front = q->front->next;
  44. 	free(temp);
  45. 	if(q->front == NULL)
  46. 		return NULL;
  47. 	else
  48. 		return q;
  49. }
  50.  
  51. int isQueueEmpty(struct queue * q)
  52. {
  53. 	if(q)
  54. 		return 0;
  55. 	else
  56. 		return 1;
  57. }
  58.  
  59. // A function to insert a number in a binary tree
  60. // Parameters - the root node and the number to insert
  61. struct binaryTreeNode * insertInBinaryTree(struct binaryTreeNode * root, int num)
  62. {
  63. 	struct binaryTreeNode * temp = NULL;
  64. 	struct queue * Q = NULL;
  65.  
  66. 	// Create a new node to insert
  67. 	struct binaryTreeNode * newNode = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
  68.  
  69. 	// Assign the values to this new node
  70. 	newNode -> data = num;
  71. 	newNode -> left = NULL;
  72. 	newNode -> right = NULL;
  73.  
  74. 	if(root == NULL)
  75. 	{
  76. 		// If the root is NULL then the newNode is inserted at root
  77. 		root = newNode;
  78. 		return root;
  79. 	}
  80.  
  81. 	// else proceed wiht the level order traversal
  82. 	Q = enQueue(Q, root);
  83.  
  84. 	while(!isQueueEmpty(Q))
  85. 	{
  86. 		temp = Q -> front -> data;
  87.  
  88. 		Q = deQueue(Q);
  89.  
  90. 		// Now we have a node of the tree in temp
  91. 		// If its left is empty we insert the node else we enqueue its
  92. 		if(temp -> left != NULL)
  93. 		{
  94. 			Q = enQueue(Q, temp -> left);
  95. 		}
  96. 		else
  97. 		{
  98. 			// Assign the new node to its left
  99. 			temp -> left = newNode;
  100.  
  101. 			// Delete the queue and return
  102. 			free(Q);
  103. 			return root;
  104. 		}
  105.  
  106. 		// Do the same for the right sub-tree of the traversed node
  107. 		if(temp -> right != NULL)
  108. 		{
  109. 			Q = enQueue(Q, temp -> right);
  110. 		}
  111. 		else
  112. 		{
  113. 			// Assign the node to its right
  114. 			temp -> right = newNode;
  115.  
  116. 			// Delete the queue and return
  117. 			free(Q);
  118. 			return root;
  119. 		}
  120. 	}
  121.  
  122. 	free(Q);
  123. 	return root;
  124. }
  125.  
  126. void levelOrder(struct binaryTreeNode * root)
  127. {
  128. 	struct binaryTreeNode * temp = NULL;
  129. 	struct queue * Q = NULL;
  130. 	if(root == NULL)
  131. 		return;
  132. 	Q = enQueue(Q, root);
  133. 	while(!isQueueEmpty(Q))
  134. 	{
  135. 		temp = Q -> front -> data;
  136. 		Q = deQueue(Q);
  137. 		printf("%d ",temp -> data);
  138. 		if(temp -> left)
  139. 			Q = enQueue(Q, temp -> left);
  140. 		if(temp -> right)
  141. 			Q = enQueue(Q, temp -> right);
  142. 	}
  143. 	free(Q);
  144. }
  145.  
  146. // Test the above functions
  147. int main(void)
  148. {
  149. 	// Initialize the tree
  150. 	struct binaryTreeNode * root = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
  151. 	root-> data = 1;
  152. 	struct binaryTreeNode * l = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
  153. 	l -> data = 2;
  154. 	struct binaryTreeNode * ll = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
  155. 	ll -> data = 4;
  156. 	ll -> left = ll -> right = NULL;
  157. 	struct binaryTreeNode * lr = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
  158. 	lr -> data = 5;
  159. 	lr -> left = lr -> right = NULL;
  160. 	l -> left = ll;
  161. 	l -> right = lr;
  162. 	struct binaryTreeNode * r = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
  163. 	r -> data = 3;
  164.  
  165. 	r -> left = r -> right = NULL;
  166.  
  167. 	root -> left = l;
  168. 	root -> right = r;
  169.  
  170. 	// print the tree
  171. 	levelOrder(root);
  172.  
  173. 	printf("\n");
  174.  
  175. 	// Insert the element
  176. 	root = insertInBinaryTree(root, 7);
  177.  
  178. 	// print again
  179. 	levelOrder(root);
  180.  
  181. 	return 0;
  182. }
Success #stdin #stdout 0s 2380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 4 5 
1 2 3 4 5 7
https://ideone.com/CFeFKF
language:
C (gcc 8.3)
created:
9 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!