Connecting all the nodes at the same level of a binary tree involves linking the right_neighbor
pointer of each node (in a tree) to its adjacent node on the same level.
Level-Order traversal refers to visiting all the nodes at the same level before iterating to the next level. In the following code, a level order traversal is done on the tree, and the right_neighbor
is set to the immediate neighbor on the same level.
#include <iostream>using namespace std;#include <queue>// A tree nodestruct Tree{char data;Tree *left;Tree *right;Tree *right_neighbor;Tree(char data){this -> data = data;left = NULL;right = NULL;right_neighbor = NULL;}};// Function to print the right_neighbor of the nodesvoid PreOrderTraversal(Tree *node){if(node == NULL){return;}else{if(node -> right_neighbor != NULL){cout << node -> data << "-> " << node -> right_neighbor -> data << endl;}else{cout << node -> data << "-> NULL" << endl;}PreOrderTraversal(node -> left);PreOrderTraversal(node -> right);}}int main() {// The treeTree *root = new Tree('a');root -> left = new Tree('b');root -> right = new Tree('c');root -> left -> left = new Tree('d');root -> left -> right = new Tree('e');queue <Tree*> Q;// Enqueue the root nodeQ.push(root);// Enqueue NULL to serve a partition between levelsQ.push(NULL);while (!Q.empty()){// Dequeue the element from the front of the queueTree *node = Q.front();Q.pop();if(node == NULL){// This shows that a level has finished, so enqueue// NULL to denote that.if(!Q.empty()){Q.push(NULL);}}else{// Peek at the element at the front of the queue and// set the right pointer to the adjacent element in the queuenode -> right_neighbor = Q.front();// Enqueue its left and right children if they existif(node -> left != NULL){Q.push(node -> left);}if(node -> right != NULL){Q.push(node -> right);}}}PreOrderTraversal(root);return 0;}
Free Resources