In C
#include <stdlib.h>
#include <stdio.h>
struct Node;
typedef struct Node Node;
struct Node
{
int data;
Node* left;
Node* right;
};
/* Private Functions */
static int* encodeNode(Node* tree, int* store);
static Node* decodeNode(int** store);
/* Public Functions */
Node* newNode(int data,Node* left,Node* right);
void deleteTree(Node* tree);
int countNodesTree(Node* tree);
int* encode(Node *tree);
Node* decode(int* store);
void printTree(Node* tree);
Node* newNode(int data,Node* left,Node* right)
{
Node* result = (Node*)malloc(sizeof(Node));
result->data = data;
result->left = left;
result->right = right;
return result;
}
void deleteTree(Node* tree)
{
if (tree == NULL)
{ return;
}
deleteTree(tree->left);
deleteTree(tree->right);
free(tree);
}
int countNodesTree(Node* tree)
{
if (tree == NULL)
{ return 0;
}
return countNodesTree(tree->left)
+ countNodesTree(tree->right)
+ 1;
}
void printTree(Node* tree)
{
if (tree == NULL)
{
fprintf(stdout, "- ");
}
else
{
fprintf(stdout, "%d ", tree->data);
printTree(tree->left);
printTree(tree->right);
}
};
The encode:
int* encode(Node *tree)
{
int nodeCount = countNodesTree(tree);
int* result = (int*)malloc(sizeof(int) * (nodeCount * 2 + 1));
// Put the node count in the first element.
// This makes it easy to also serialize this object for transport
// i.e. you can put it in a file or a stream (socket) and easily recover it.
result[0] = nodeCount;
encodeNode(tree, result + 1);
return result;
}
int* encodeNode(Node* tree, int* store)
{
if (tree != NULL)
{
store[0] = tree->data;
/*
* Slight overkill. for this question.
* But works and makes future enhancement easy
*/
store[1] = (tree->left == NULL ? 0 : 1)
+ (tree->right == NULL ? 0 : 2);
store += 2;
store = encodeNode(tree->left, store);
store = encodeNode(tree->right, store);
}
return store;
}
The decode:
Node* decode(int* store)
{
if (store == NULL)
{ fprintf(stderr, "Bad Input terminating: encode() always return non NULL\n");
exit(1);
}
if (store[0] == 0)
{
return NULL;
}
store++;
return decodeNode(&store);
}
Node* decodeNode(int** store)
{
int value = (*store)[0];
int flag = (*store)[1];
(*store) += 2;
Node* left = flag & 1 ? decodeNode(store) : NULL;
Node* right = flag & 2 ? decodeNode(store) : NULL;
return newNode(value, left, right);
}
Main:
int main()
{
Node* t = newNode(5,
newNode(3, NULL, NULL),
newNode(2,
newNode(2,
newNode(9, NULL, NULL),
newNode(9, NULL, NULL)
),
newNode(1, NULL, NULL)
)
);
printTree(t);
fprintf(stdout,"\n");
int* e = encode(t);
Node* d = decode(e);
printTree(d);
fprintf(stdout,"\n");
free(e);
deleteTree(d);
deleteTree(t);
}
Note. Each node is encoded as two integers (plus one int for the count of nodes).
So the supplied tree encodes like this:
7, 5, 3, 3, 0, 2, 3, 2, 3, 9, 0, 9, 0 1, 0
^ ^
^ ^ Node 1
^
Count
In your example, isn't '3' an internal node? Because it doesn't have exactly two non empty descendants. Ah - a leaf isn't an internal node? I guess I didn't get the question. Is
a == encode (decode (a))
everything I have to reach with my tree? – user unknown – 2011-05-07T18:48:41.8971Input and output requirements wouldn't hurt. – Yasir Arsanukaev – 2011-02-01T18:11:54.480
2@Yasir: The encoding algorithm is your job so I cannot provide any input and output.
int *
is a black box for user. – Alexandru – 2011-02-01T18:14:30.567Are there on any restrictions on the range of integers? More specifically if we use a language with arbitrarily large integers are we allowed to make use of that? And is the size of the encoded data measured in number of integers or number of bytes? – sepp2k – 2011-02-01T20:07:22.417
Do the encode and decode functions need to be side-effect free (other than memory allocation)? Or may they for example store data in global variables? – sepp2k – 2011-02-01T20:08:33.037
Yet another question: Do you measure average encoding length or worst case encoding length? – sepp2k – 2011-02-01T20:15:15.777
@sepp2k. 1) Arbitrary large integers are ok. However the only allowed sentinel is 0. You can encode lengths if you want. 2) Ideally it is side-effect free, but not necessary. 3) Average encoding length. – Alexandru – 2011-02-01T20:18:14.343
@Alex: Sorry to nag, but are we counting number of bytes or number of integers? I'm asking because I'm thinking of a solution where
encode
always returns a list of two integers, but the second one may be very large. – sepp2k – 2011-02-01T20:26:53.263@sepp2k. Number of bytes. Any sequence of bytes can be interpreted as an integer. – Alexandru – 2011-02-01T20:35:31.210
1Assuming the data integers themselves are actual 32-bit integers, there is a simple encoding that uses only 32*n bits. – Anon. – 2011-02-01T21:07:30.017
Crap...I finished implementing a solution before I realized you wanted a binary tree and not a binary search tree. Much less structure in a binary tree... – Daniel Standage – 2011-02-02T04:43:10.050
Ok, posted an actual solution! – Daniel Standage – 2011-02-02T20:45:29.630