How to implement a Binary Tree using Queue powered by Linked List in C
Hello Friends, this is the project that I have been working from the past two days. When I have to implement a tree using the Queue concept, I was thinking to implement this using a linked list powered Queue. So I have used the idea of Queue but implemented using Linked List.
Many other websites have implemented the same using an array storing the double pointers of tree nodes. But, I bet you implementing utilising the concept of keeping these double pointers of tree nodes into Queue nodes is super interesting.
// Tree node storing data with two other tree pointers
typedef struct Tree_Node{
int data; //data for tree_node
struct Tree_Node* Left_Child; //pointer to left child
struct Tree_Node* Right_Child; //pointer to right child
}Tree_Node;
Tree_Node *Root=NULL;//Queue which will store addresses of Tree_Nodes
typedef struct Queue{
struct Tree_Node **data; //Pointer to a Tree_Node
struct Queue* next; //Pointer to next Queue_Node
}Queue;
Queue *Front=NULL, *Rear=NULL;
Now the main task is to write the Enqueue and Dequeue function that will help our queue to work like a “Queue”. So a trick in these types of programs is that we are just implementing only one Tree or Queue in our program, that what makes our work more comfortable for right now as all the member functions get access to the global pointers Head and Rear.
So if you want to implement multiple Tree or any linked structure more than once try to avoid using global pointers for that. One way is to pass the working pointers to the member functions so that they can change them appropriately. Anyway, we are implementing using that global thing which reduces my work to update Head and Rear pointers for a specific tree as we are taking just one tree in our program.
One rule that you should follow is that when you code for Queue then think from a Queue’s point of view, things such as storing that ‘data’ and connecting it properly with another node and using FIFO fashion. So when you code for Queue think the double-pointer of Tree Node as main data for this Queue to store. Queue and Dequeue will follow their regular fashion.
So if you have created a Queue using an array concept, it's okay, but it is not. It has some certain bounds that you don't want. Maybe in some programs, it is a good practice to allocate the memory in the starting, but you need to learn this forever extending technique using the concept of the linked list also.
void Enqueue( Tree_Node **data)
{
Queue* temp;
temp = (Queue*)malloc(sizeof(Queue));
temp->data = data;
temp->next = NULL;if(Front==NULL){ Front = Rear = temp; }
else
{
Rear->next = temp;
Rear = temp;
}
}Tree_Node** Dequeue()
{
if(Rear!=NULL)
{
if(!Front->next)
{
Tree_Node **p;
p = Front->data;
free(Front);
Front=Rear=NULL;
return p;
}
else
{
Tree_Node **p;
Queue* q;
q = Front;
p = Front->data;
Front = Front->next;
free(q);
return p;
}
}
return NULL;
}
Now once you code the active Queue, you are ready to go in any fashion. The node of the tree is storing some data in itself and storing two other pointers, one for its left child and other for the right child. Another confusing part may be how these double pointers are handled here. But you have to code and get these fundamental concepts of pointers and dereferencing the address and gaining access to even changing the data stored in memory locations.
So here I am passing the function to adding nodes in the main tree.
void Add_To_Tree(int num)
{
if(!Root)
{
Root = (Tree_Node*)malloc(sizeof(Tree_Node));
Root->data = num;
Root->Left_Child = Root->Right_Child = NULL;Enqueue(&Root->Left_Child);
Enqueue(&Root->Right_Child);}
else
{
Tree_Node** t;t = Dequeue();
(*t) = (Tree_Node*)malloc(sizeof(Tree_Node));
(*t)->data = num;
(*t)->Left_Child = (*t)->Right_Child = NULL;
Enqueue(&(*t)->Left_Child);
Enqueue(&(*t)->Right_Child);
}
}
Once you understand how to manipulate these functions using their parameters and return types, you can easily make further derived concepts by just messing these concepts here and there. Still, I am attaching a simple main() function to add ‘some’ node to the tree and an essential printing function for the tree.
void Print_My_Tree(Tree_Node* x)
{
if(x)
{
printf(“..%d..\n”, x->data);if(x->Left_Child)
Print_My_Tree(x->Left_Child);
if(x->Right_Child)
Print_My_Tree(x->Right_Child);
}
}int main(){
int n;
printf(“ Enter How many nodes “);
scanf(“%d”, &n);
for(int i=0; i<n; i++) { Add_To_Tree(i); }
Print_My_Tree(Root);
return 0;
}
So this method has the flexibility of adding even thousands of nodes that naughty programmers want sometimes.
Thank you for reading this article, and I hope this helps otherwise Google and Youtube are there for you always.
Happy Learning (: — ——:)
/* Ping me up for any queries akcgjc007@gmail.com */
