Succinct Encoding of Binary Tree | C ++ program to demonstrate Succinct Tree Encoding and decoding ; A Binary Tree Node ; Utility function to create new Node ; This function fills lists ' struc ' and ' data ' . ' struc ' list stores structure information . ' data ' list stores tree data ; If root is NULL , put 0 in structure array and return ; Else place 1 in structure array , key in ' data ' array and recur for left and right children ; Constructs tree from ' struc ' and ' data ' ; Remove one item from structure list ; If removed bit is 1 , ; remove an item from data list ; Create a tree node with the removed data ; And recur to create left and right subtrees ; A utility function to print tree ; Driver program ; Let us construct the Tree shown in the above figure ; Structure iterator ; Data iterator
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; struct Node * left , * right ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> key = key ; temp -> left = temp -> right = NULL ; return ( temp ) ; } void EncodeSuccinct ( Node * root , list < bool > & struc , list < int > & data ) { if ( root == NULL ) { struc . push_back ( 0 ) ; return ; } struc . push_back ( 1 ) ; data . push_back ( root -> key ) ; EncodeSuccinct ( root -> left , struc , data ) ; EncodeSuccinct ( root -> right , struc , data ) ; } Node * DecodeSuccinct ( list < bool > & struc , list < int > & data ) { if ( struc . size ( ) <= 0 ) return NULL ; bool b = struc . front ( ) ; struc . pop_front ( ) ; if ( b == 1 ) { int key = data . front ( ) ; data . pop_front ( ) ; Node * root = newNode ( key ) ; root -> left = DecodeSuccinct ( struc , data ) ; root -> right = DecodeSuccinct ( struc , data ) ; return root ; } return NULL ; } void preorder ( Node * root ) { if ( root ) { cout << " key : ▁ " << root -> key ; if ( root -> left ) cout << " ▁ | ▁ left ▁ child : ▁ " << root -> left -> key ; if ( root -> right ) cout << " ▁ | ▁ right ▁ child : ▁ " << root -> right -> key ; cout << endl ; preorder ( root -> left ) ; preorder ( root -> right ) ; } } int main ( ) { Node * root = newNode ( 10 ) ; root -> left = newNode ( 20 ) ; root -> right = newNode ( 30 ) ; root -> left -> left = newNode ( 40 ) ; root -> left -> right = newNode ( 50 ) ; root -> right -> right = newNode ( 70 ) ; cout << " Given ▁ Tree STRNEWLINE " ; preorder ( root ) ; list < bool > struc ; list < int > data ; EncodeSuccinct ( root , struc , data ) ; cout << " Encoded Tree " cout << " Structure ▁ List STRNEWLINE " ; list < bool > :: iterator si ; for ( si = struc . begin ( ) ; si != struc . end ( ) ; ++ si ) cout << * si << " ▁ " ; cout << " Data List " list < int > :: iterator di ; for ( di = data . begin ( ) ; di != data . end ( ) ; ++ di ) cout << * di << " ▁ " ; Node * newroot = DecodeSuccinct ( struc , data ) ; cout << " Preorder traversal of decoded tree " ; preorder ( newroot ) ; return 0 ; }