// 赫夫曼樹.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"

#include <string.h> 
#include <stdio.h> 
#define Max_Node 1000 
#define Max_Weight  1000 


typedef struct HuffmanTreeNode 
      {    char ch, code[20]; 
           int weight; 
           int parent, lchild, rchild; 
            }HTNode, *HuffmanTree; 
typedef struct 
    {    HTNode arr[Max_Node]; 
         int total; 
            } HTree; 

 int statistic_char(char *text, HTree *t) 
   { 
        int i, j; 
        int text_len = strlen(text); 
        t->total = 0; 
        for (i=0; i<text_len; i++) 
         { for (j=0;j<t->total ; j++) 
           if (t->arr[j].ch == text[i]) 
			{  
              t->arr[j].weight ++; 
              break; } 
            if (j==t->total) 
            {  
              t->arr[t->total].ch = text[i]; 
              t->arr[t->total].weight = 1; 
              t->total ++; } 
            } 
        printf("各字符的出現頻率分別為\n"); 
        for (i=0; i<t->total; i++) 
        printf("'%c'  %d\n", t->arr[i].ch, t->arr[i].weight); 
        printf("\n"); 
        return t->total; 
 } 
int create_htree(HTree *t) 
    { 
       int i; 
       int total_node = t->total * 2 - 1; 
       int min1, min2; 
       int min1_i, min2_i; 
       int leaves = t->total;  
       for (i=0; i<leaves; i++) 
            {  t->arr[i].parent = -1; 
               t->arr[i].rchild = -1; 
               t->arr[i].lchild = -1; } 
        while (t->total < total_node) 
            { min1 = min2 = Max_Weight; 
              for (i=0; i<t->total; i++) 
			  {if (t->arr[i].parent == -1&& t->arr[i].weight < min2) 
			   { if (t->arr[i].weight < min1) 
			    {   min2_i = min1_i;  min2 = min1; 
                    min1_i = i;    min1 = t->arr[i].weight; } 
              else 
			  {   min2_i = i;    min2 = t->arr[i].weight; } } } 
            t->arr[t->total].weight = min1 + min2; 
            t->arr[t->total].parent = -1; 
            t->arr[t->total].lchild = min1_i; 
            t->arr[t->total].rchild = min2_i; 
            t->arr[min1_i].parent = t->total; 
            t->arr[min2_i].parent = t->total; 
            t->arr[t->total].ch = ' '; 
            t->total ++; } 
            return 0; 
  } 

void print_htree_ldr(HTree *t, int head_i, int deep, int* path) 
{ int i; 
  if (head_i == -1) return; 
  path[deep] = 0; 
  print_htree_ldr(t, t->arr[head_i].lchild, deep + 1, path); 
  if (deep) printf("      "); 
  for (i=1; i<deep; i++) 
  printf("%s", path[i]==path[i-1]?"      ":"│    "); 
  int dir = path[i]==path[i-1]; 
  if ( t->arr[head_i].lchild == -1 && t->arr[head_i].rchild == -1) 
      printf("%s—— %d '%c'\n", dir? "┌":"└", 
      t->arr[head_i].weight, t->arr[head_i].ch); 
  else if (head_i != t->total-1) 
       printf("%s—%02d┤\n", dir? "┌":"└", t->arr[head_i].weight); 
   else 
        printf("    %02d┤\n", t->arr[head_i].weight); 
        path[deep] = 1; 
        print_htree_ldr(t, t->arr[head_i].rchild, deep + 1, path); 
}

int main(int argc, char* argv[]) 
{ HTree t; 
  char text[128]={0}; 
  printf("請輸入你需要處理的字符串："); 
  gets(text); 
  char code[128] = ""; 
  int path[16]={0}; 
  statistic_char(text, &t); 
  create_htree(&t); 
  print_htree_ldr(&t, t.total-1, 0, path);
  return 0; 
}