Linked complete binary tree & its creation | GeeksforGeeks
A complete binary tree is a binary tree where each level ‘l’ except the last has 2^l nodes and the nodes at the last level are all left aligned. Complete binary trees are mainly used in heap based data structures.
The nodes in the complete binary tree are inserted from left to right in one level at a time. If a level is full, the node is inserted in a new level.
The array representation is better because it doesn’t contain any empty slot. Given parent index i, its left child is given by 2 * i + 1 and its right child is given by 2 * i + 2.
However, it may be an interesting programming question to created a Complete Binary Tree using linked representation.
To create a linked complete binary tree, we need to keep track of the nodes in a level order fashion such that the next node to be inserted lies in the leftmost position. A queue data structure can be used to keep track of the inserted nodes.
To created a Complete Binary Tree using linked representation.
Read full article from Linked complete binary tree & its creation | GeeksforGeeks
A complete binary tree is a binary tree where each level ‘l’ except the last has 2^l nodes and the nodes at the last level are all left aligned. Complete binary trees are mainly used in heap based data structures.
The nodes in the complete binary tree are inserted from left to right in one level at a time. If a level is full, the node is inserted in a new level.
The array representation is better because it doesn’t contain any empty slot. Given parent index i, its left child is given by 2 * i + 1 and its right child is given by 2 * i + 2.
However, it may be an interesting programming question to created a Complete Binary Tree using linked representation.
To create a linked complete binary tree, we need to keep track of the nodes in a level order fashion such that the next node to be inserted lies in the leftmost position. A queue data structure can be used to keep track of the inserted nodes.
To created a Complete Binary Tree using linked representation.
1. If the tree is empty, initialize the root with new node.
2. Else, get the front node of the queue.
…….If the left child of this front node doesn’t exist, set the left child as the new node.
…….else if the right child of this front node doesn’t exist, set the right child as the new node.
…….If the left child of this front node doesn’t exist, set the left child as the new node.
…….else if the right child of this front node doesn’t exist, set the right child as the new node.
3. If the front node has both the left child and right child, Dequeue() it.
4. Enqueue() the new node.
void insert(struct node **root, int data, struct Queue* queue){ // Create a new node for given data struct node *temp = newNode(data); // If the tree is empty, initialize the root with new node. if (!*root) *root = temp; else { // get the front node of the queue. struct node* front = getFront(queue); // If the left child of this front node doesn’t exist, set the // left child as the new node if (!front->left) front->left = temp; // If the right child of this front node doesn’t exist, set the // right child as the new node else if (!front->right) front->right = temp; // If the front node has both the left child and right child, // Dequeue() it. if (hasBothChild(front)) Dequeue(queue); } // Enqueue() the new node for later insertions Enqueue(temp, queue);} for(i = 1; i <= 12; ++i) insert(&root, i, queue);