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 code ; Let us conthe Tree shown in the above figure ; Structure iterator ; Data iterator
using System ; using System . Collections . Generic ; class GFG { public class Node { public int key ; public Node left , right ; } ; static Node newNode ( int key ) { Node temp = new Node ( ) ; temp . key = key ; temp . left = temp . right = null ; return ( temp ) ; } static List < Boolean > struc ; static List < int > 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 . Count <= 0 ) return null ; bool b = struc [ 0 ] ; struc . RemoveAt ( 0 ) ; if ( b == true ) { int key = data [ 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 ) { Console . Write ( " key : ▁ " + root . key ) ; if ( root . left != null ) Console . Write ( " ▁ left ▁ child : ▁ " + root . left . key ) ; if ( root . right != null ) Console . Write ( " ▁ right ▁ child : ▁ " + root . right . key ) ; Console . WriteLine ( ) ; 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 ) ; Console . Write ( " Given ▁ Tree STRNEWLINE " ) ; preorder ( root ) ; struc = new List < Boolean > ( ) ; data = new List < int > ( ) ; EncodeSuccinct ( root ) ; Console . Write ( " STRNEWLINE Encoded ▁ Tree STRNEWLINE " ) ; Console . Write ( " Structure ▁ List STRNEWLINE " ) ; foreach ( bool si in struc ) { if ( si == true ) Console . Write ( 1 + " ▁ " ) ; else Console . Write ( 0 + " ▁ " ) ; } Console . Write ( " STRNEWLINE Data ▁ List STRNEWLINE " ) ; foreach ( int di in data ) Console . Write ( di + " ▁ " ) ; Node newroot = DecodeSuccinct ( ) ; Console . Write ( " STRNEWLINE STRNEWLINE Preorder ▁ traversal " + " of ▁ decoded ▁ tree STRNEWLINE " ) ; preorder ( newroot ) ; } }