A succinct encoding of Binary Tree takes close to minimum possible space. The number of structurally different binary trees on n nodes is n’th Catalan number. For large n, this is about 4n; thus we need at least about log2 4 n = 2n bits to encode it. A succinct binary tree therefore would occupy 2n+o(n) bits.
One simple representation which meets this bound is to visit the nodes of the tree in preorder, outputting “1” for an internal node and “0” for a leaf. If the tree contains data, we can simply simultaneously store it in a consecutive array in preorder.
Below is algorithm for encoding:
function EncodeSuccinct(node n, bitstring structure, array data) {
if n = nil then
append 0 to structure;
else
append 1 to structure;
append n.data to data;
EncodeSuccinct(n.left, structure, data);
EncodeSuccinct(n.right, structure, data);
}
And below is algorithm for decoding
function DecodeSuccinct(bitstring structure, array data) {
remove first bit of structure and put it in b
if b = 1 then
create a new node n
remove first element of data and put it in n.data
n.left = DecodeSuccinct(structure, data)
n.right = DecodeSuccinct(structure, data)
return n
else
return nil
}
Source: https://en.wikipedia.org/wiki/Binary_tree#Succinct_encodings
Example:
Input:
10
/
20 30
/
40 50 70
Data Array (Contains preorder traversal)
10 20 40 50 30 70
Structure Array
1 1 1 0 0 1 0 0 1 0 1 0 0
1 indicates data and 0 indicates NULL
Below is C++ implementation of above algorithms.
C++
// C++ program to demonstrate Succinct Tree Encoding and decoding #include<bits/stdc++.h> using namespace std; // A Binary Tree Node struct Node { int key; struct Node* left, *right; }; // Utility function to create new Node Node *newNode(int key) { Node *temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp); } // This function fills lists 'struc' and 'data'. 'struc' list // stores structure information. 'data' list stores tree data void EncodeSuccinct(Node *root, list<bool> &struc, list<int> &data) { // If root is NULL, put 0 in structure array and return if (root == NULL) { struc.push_back(0); return; } // Else place 1 in structure array, key in 'data' array // and recur for left and right children struc.push_back(1); data.push_back(root->key); EncodeSuccinct(root->left, struc, data); EncodeSuccinct(root->right, struc, data); } // Constructs tree from 'struc' and 'data' Node *DecodeSuccinct(list<bool> &struc, list<int> &data) { if (struc.size() <= 0) return NULL; // Remove one item from from structure list bool b = struc.front(); struc.pop_front(); // If removed bit is 1, if (b == 1) { // remove an item from data list int key = data.front(); data.pop_front(); // Create a tree node with the removed data Node *root = newNode(key); // And recur to create left and right subtrees root->left = DecodeSuccinct(struc, data); root->right = DecodeSuccinct(struc, data); return root; } return NULL; } // A utility function to print tree 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); } } // Driver program int main() { // Let us construct the Tree shown in the above figure 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
"; preorder(root); list<bool> struc; list<int> data; EncodeSuccinct(root, struc, data); cout << "
Encoded Tree
"; cout << "Structure List
"; list<bool>::iterator si; // Structure iterator for (si = struc.begin(); si != struc.end(); ++si) cout << *si << " "; cout << "
Data List
"; list<int>::iterator di; // Data iIterator 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; } |
Python
# Python program to demonstrate Succient Tree Encoding and Decoding # Node structure class Node: # Utility function to create new Node def __init__(self , key): self.key = key self.left = None self.right = None def EncodeSuccint(root , struc , data): # If root is None , put 0 in structure array and return if root is None : struc.append(0) return # Else place 1 in structure array, key in 'data' array # and recur for left and right children struc.append(1) data.append(root.key) EncodeSuccint(root.left , struc , data) EncodeSuccint(root.right , struc ,data) # Constructs tree from 'struc' and 'data' def DecodeSuccinct(struc , data): if(len(struc) <= 0): return None # Remove one item from structure list b = struc[0] struc.pop(0) # If removed bit is 1 if b == 1: key = data[0] data.pop(0) #Create a tree node with removed data root = Node(key) #And recur to create left and right subtrees root.left = DecodeSuccinct(struc , data); root.right = DecodeSuccinct(struc , data); return root return None def preorder(root): if root is not None: print "key: %d" %(root.key), if root.left is not None: print "| left child: %d" %(root.left.key), if root.right is not None: print "| right child %d" %(root.right.key), print "" preorder(root.left) preorder(root.right) # Driver Program root = Node(10) root.left = Node(20) root.right = Node(30) root.left.left = Node(40) root.left.right = Node(50) root.right.right = Node(70) print "Given Tree"preorder(root) struc = [] data = [] EncodeSuccint(root , struc , data) print "
Encoded Tree"print "Structure List" for i in struc: print i , print "
DataList"for value in data: print value, newroot = DecodeSuccinct(struc , data) print "
Preorder Traversal of decoded tree"preorder(newroot) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
Output:
Given Tree key: 10 | left child: 20 | right child: 30 key: 20 | left child: 40 | right child: 50 key: 40 key: 50 key: 30 | right child: 70 key: 70 Encoded Tree Structure List 1 1 1 0 0 1 0 0 1 0 1 0 0 Data List 10 20 40 50 30 70 Preorder traversal of decoded tree key: 10 | left child: 20 | right child: 30 key: 20 | left child: 40 | right child: 50 key: 40 key: 50 key: 30 | right child: 70 key: 70
This article is contribute by Shivam. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
leave a comment
0 Comments