Succinct Encoding of Binary Tree | Java 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 code ; Let us conthe Tree shown in the above figure ; Structure iterator ; Data iterator
import java . util . * ; class GFG { static class Node { int key ; Node left , right ; } ; static Node newNode ( int key ) { Node temp = new Node ( ) ; temp . key = key ; temp . left = temp . right = null ; return ( temp ) ; } static Vector < Boolean > struc ; static Vector < Integer > data ; static Node root ; static void EncodeSuccinct ( Node root ) { if ( root == null ) { struc . add ( false ) ; return ; } struc . add ( true ) ; data . add ( root . key ) ; EncodeSuccinct ( root . left ) ; EncodeSuccinct ( root . right ) ; } static Node DecodeSuccinct ( ) { if ( struc . size ( ) <= 0 ) return null ; boolean b = struc . get ( 0 ) ; struc . remove ( 0 ) ; if ( b == true ) { int key = data . get ( 0 ) ; data . remove ( 0 ) ; Node root = newNode ( key ) ; root . left = DecodeSuccinct ( ) ; root . right = DecodeSuccinct ( ) ; return root ; } return null ; } static void preorder ( Node root ) { if ( root != null ) { System . out . print ( " key : ▁ " + root . key ) ; if ( root . left != null ) System . out . print ( " ▁ left ▁ child : ▁ " + root . left . key ) ; if ( root . right != null ) System . out . print ( " ▁ right ▁ child : ▁ " + root . right . key ) ; System . out . println ( ) ; preorder ( root . left ) ; preorder ( root . right ) ; } } public static void main ( String [ ] args ) { 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 ) ; System . out . print ( "Given TreeNEW_LINE"); preorder ( root ) ; struc = new Vector < > ( ) ; data = new Vector < > ( ) ; EncodeSuccinct ( root ) ; System . out . print ( " Encoded Tree "); System . out . print ( "Structure ListNEW_LINE"); for ( boolean si : struc ) { if ( si == true ) System . out . print ( 1 + " ▁ " ) ; else System . out . print ( 0 + " ▁ " ) ; } System . out . print ( " Data List "); for ( int di : data ) System . out . print ( di + " ▁ " ) ; Node newroot = DecodeSuccinct ( ) ; System . out . print ( " Preorder traversal " ▁ + ▁ " of decoded tree "); preorder ( newroot ) ; } }