Construct the full k | C ++ program to build full k - ary tree from its preorder traversal and to print the postorder traversal of the tree . ; Structure of a node of an n - ary tree ; Utility function to create a new tree node with k children ; Function to build full k - ary tree ; For null tree ; For adding k children to a node ; Check if ind is in range of array Check if height of the tree is greater than 1 ; Recursively add each child ; Function to find the height of the tree ; Function to print postorder traversal of the tree ; Driver program to implement full k - ary tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; vector < Node * > child ; } ; Node * newNode ( int value ) { Node * nNode = new Node ; nNode -> key = value ; return nNode ; } Node * BuildKaryTree ( int A [ ] , int n , int k , int h , int & ind ) { if ( n <= 0 ) return NULL ; Node * nNode = newNode ( A [ ind ] ) ; if ( nNode == NULL ) { cout << " Memory ▁ error " << endl ; return NULL ; } for ( int i = 0 ; i < k ; i ++ ) { if ( ind < n - 1 && h > 1 ) { ind ++ ; nNode -> child . push_back ( BuildKaryTree ( A , n , k , h - 1 , ind ) ) ; } else { nNode -> child . push_back ( NULL ) ; } } return nNode ; } Node * BuildKaryTree ( int * A , int n , int k , int ind ) { int height = ( int ) ceil ( log ( ( double ) n * ( k - 1 ) + 1 ) / log ( ( double ) k ) ) ; return BuildKaryTree ( A , n , k , height , ind ) ; } void postord ( Node * root , int k ) { if ( root == NULL ) return ; for ( int i = 0 ; i < k ; i ++ ) postord ( root -> child [ i ] , k ) ; cout << root -> key << " ▁ " ; } int main ( ) { int ind = 0 ; int k = 3 , n = 10 ; int preorder [ ] = { 1 , 2 , 5 , 6 , 7 , 3 , 8 , 9 , 10 , 4 } ; Node * root = BuildKaryTree ( preorder , n , k , ind ) ; cout << " Postorder ▁ traversal ▁ of ▁ constructed " " ▁ full ▁ k - ary ▁ tree ▁ is : ▁ " ; postord ( root , k ) ; cout << endl ; return 0 ; }