I am trying to implement a levelOrder funtion which takes pointer of tree and prints the data of tree level-by-level. This is a question from the book C How to Program and the full question is given below:
(Level Order Binary Tree Traversal) The program of Fig. 12.19 illustrated three recursive methods of traversing a binary tree—inorder traversal, preorder traversal, and postorder traversal. This exercise presents the level order traversal of a binary tree in which the node values are printed level-by-level starting at the root node level. The nodes on each level are printed from left to right. The level order traversal is not a recursive algorithm. It uses the queue data structure to control the output of the nodes. The algorithm is as follows:
Insert the root node in the queue
While there are nodes left in the queue,
Get the next node in the queue
Print the node’s value
If the pointer to the left child of the node is not NULL Insert the left child node in the queue
If the pointer to the right child of the node is not NULL
Insert the right child node in the queue.Write function levelOrder to perform a level order traversal of a binary tree. The function should take as an argument a pointer to the root node of the binary tree. Modify the program of Fig. 12.19 to use this function. Compare the output from this function to the outputs of the other traversal algorithms to see that it worked correctly. [Note: You’ll also need to modify and incor- porate the queue-processing functions of Fig. 12.13 in this program.]
My try is below:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct treeNode{
struct treeNode* left;
int data;
struct treeNode* right;
};
struct queueNode{
struct treeNode* tree;
struct queueNode* next;
};
/* prototype */
void insert(struct treeNode**, int); // tree creator
void levelOrder(struct treeNode**);
void inOrder(struct treeNode*);
void enqueue(struct queueNode**, struct queueNode**, struct treeNode*);
struct treeNode* dequeue(struct queueNode**, struct queueNode**);
int main(){
struct treeNode* root = NULL;
levelOrder(&root);
}
void insert(struct treeNode** root, int val){
if(!(*root)){ // when root is empty
*root = (struct treeNode*)malloc(sizeof(struct treeNode));
if(*root){ // if allocation is achieved
(*root) -> data = val;
(*root) -> right = NULL;
(*root) -> left = NULL;
} else { // if allocation is not succesfull
printf("%s\n", "[ERROR] Not enough memory space for allocation!");
}
} else { // if root is not empty
if(val > (*root) -> data)
insert(&(*root) -> right, val);
else if(val < (*root) -> data)
insert(&(*root) -> left, val);
}
}
void enqueue(struct queueNode** head, struct queueNode** tail, struct treeNode* tree){
struct queueNode* newNode = (struct queueNode*)malloc(sizeof(struct queueNode));
if( newNode ){
newNode -> tree = tree;
newNode -> next = NULL;
if(!(*head)){
*head = newNode;
//printf("head->tree->data:%d --> ", (*head)->tree->data);
printf("%d --> ", (*head)->tree->data);
}
else{
(*tail) -> next = newNode;
//printf("tail->tree->data:%d --> ", (*tail)->tree->data);
printf("%d --> ", (*tail)->tree->data);
}
(*tail) = newNode;
} else {
printf("%s\n", "[ERROR] Not enough memory space for allocation!");
}
}
struct treeNode* dequeue(struct queueNode** head, struct queueNode** tail){
struct treeNode* val = (*head)->tree;
struct queueNode* temp = *head;
*head = (*head) -> next;
if(!(*head))
*tail = NULL;
return val;
}
void levelOrder(struct treeNode** root){
struct treeNode* output = NULL;
struct queueNode* head = NULL, *tail = NULL;
size_t i;
srand(time(NULL));
for(i = 0; i < 9; ++i){
insert(root, 1 + rand()%16);
}
puts("in order");
inOrder(*root);
puts("NULL");
puts("After in order");
enqueue(&head, &tail, *root);
while(head){
if(head->tree->left)
enqueue(&head, &tail, head->tree->left);
if(head->tree->right)
enqueue(&head, &tail, head->tree->right);
head = head->next;
}
/*for(i=0;i<9;++i){
output = dequeue(&head, &tail);
printf("%d",output->data);
}*/
}
void inOrder(struct treeNode* tree){ // used to be sure if my implementation works correct
if(tree != NULL){
inOrder(tree->left);
printf("%-2d-->", tree->data);
inOrder(tree->right);
}
}
When I use dequeue function, it does not work correctly. I cannot get all trees in the queue with dequeue function. However, if I print the values in enqueue as seen, it prints all the value added except one(I do not which one) but prints the first value twice. (Can you please run the code? I wanted to put the outputs here, but stackoverflow thinks it as a code block and I cannot edit it so it did not let me add it.)
