//
// Torbert, 8.12.2009
//

#include <stdio.h>
#include <stdlib.h>

#define N 256

typedef struct tree_node
{
	char					symb;
	int					freq;
	struct tree_node* left;
	struct tree_node* right;
} node;

int node_cmp(const void* a, const void* b) // pointers!
{
	const node** x = (const node**)a;       // double indirection
	const node** y = (const node**)b;
	const node*  w = *x;
	const node*  z = *y;
	return -(w->freq - z->freq);
}
void display(node* t, int n) // tilt your head to see the tree
{
	int k;
	if(t==NULL) return;
	display(t->right,n+1);    // trick, go right first
	for(k=0; k<2*n; k++)
		printf("   ");
	if(n>0)
		printf("---");
	printf("%c(%d)\n",t->symb,t->freq);
	printf("\n");
	display(t->left,n+1);
}
int main(int argc, char* argv[])
{
	node*	t[N];
	int	j,numtrees=1;

	t[6]=(node*)malloc(sizeof(node)); // build tree by hand, yikes!
	t[6]->symb='o';
	t[6]->freq=1;
	t[6]->left=NULL;   // leaf
	t[6]->right=NULL;

	t[5]=(node*)malloc(sizeof(node));
	t[5]->symb='l';
	t[5]->freq=2;
	t[5]->left=NULL;   // leaf
	t[5]->right=NULL;

	t[4]=(node*)malloc(sizeof(node));
	t[4]->symb='e';
	t[4]->freq=1;
	t[4]->left=NULL;   // leaf
	t[4]->right=NULL;

	t[3]=(node*)malloc(sizeof(node));
	t[3]->symb='h';
	t[3]->freq=1;
	t[3]->left=NULL;   // leaf
	t[3]->right=NULL;

	t[2]=(node*)malloc(sizeof(node));
	t[2]->symb='*';
	t[2]->freq=2;
	t[2]->left=t[4];   // not a leaf
	t[2]->right=t[6];

	t[1]=(node*)malloc(sizeof(node));
	t[1]->symb='*';
	t[1]->freq=3;
	t[1]->left=t[2];   // not a leaf
	t[1]->right=t[3];

	t[0]=(node*)malloc(sizeof(node));
	t[0]->symb='*';
	t[0]->freq=3;
	t[0]->left=t[1];   // not a leaf
	t[0]->right=t[5];

	qsort(t,numtrees,sizeof(node*),node_cmp);

	for(j=0;j<numtrees;j++)
	{
		display(t[j],0);
		printf("==============================\n");
	}

	return 0;
}