Creating a tree with Left | C ++ program to create a tree with left child right sibling representation . ; Creating new Node ; Adds a sibling to a list with starting with n ; Add child Node to a Node ; Check if child list is not empty . ; Traverses tree in level order ; Corner cases ; Create a queue and enque root ; Take out an item from the queue ; Print next level of taken out item and enque next level 's children ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next ; struct Node * child ; } ; Node * newNode ( int data ) { Node * newNode = new Node ; newNode -> next = newNode -> child = NULL ; newNode -> data = data ; return newNode ; } Node * addSibling ( Node * n , int data ) { if ( n == NULL ) return NULL ; while ( n -> next ) n = n -> next ; return ( n -> next = newNode ( data ) ) ; } Node * addChild ( Node * n , int data ) { if ( n == NULL ) return NULL ; if ( n -> child ) return addSibling ( n -> child , data ) ; else return ( n -> child = newNode ( data ) ) ; } void traverseTree ( Node * root ) { if ( root == NULL ) return ; cout << root -> data << " ▁ " ; if ( root -> child == NULL ) return ; queue < Node * > q ; Node * curr = root -> child ; q . push ( curr ) ; while ( ! q . empty ( ) ) { curr = q . front ( ) ; q . pop ( ) ; while ( curr != NULL ) { cout << curr -> data << " ▁ " ; if ( curr -> child != NULL ) { q . push ( curr -> child ) ; } curr = curr -> next ; } } } int main ( ) { Node * root = newNode ( 10 ) ; Node * n1 = addChild ( root , 2 ) ; Node * n2 = addChild ( root , 3 ) ; Node * n3 = addChild ( root , 4 ) ; Node * n4 = addChild ( n3 , 6 ) ; Node * n5 = addChild ( root , 5 ) ; Node * n6 = addChild ( n5 , 7 ) ; Node * n7 = addChild ( n5 , 8 ) ; Node * n8 = addChild ( n5 , 9 ) ; traverseTree ( root ) ; return 0 ; }