二叉树，哈夫曼

        二叉树也是 递归 定 义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

•  空二叉树——(a)；
  
• 只有一个根结点的二叉树——(b)；
• 右子树为空的二叉树——(c)；
• 左子树为空的二叉树——(d)；
• 完全二叉树——(e)   注意：尽管二叉树与树有许多相似之处，但二叉树是树的特殊情形。

      二叉树的递归一直是一个另大家纠结的问题。尤其是二叉树的非递归，十分令人头痛。
      

void walk(BTree * node)
{
   for(;;) {
                  if(node==NULL)
                       return ;
                   walk(node->left);
                   printf("%d ",node->data);
                   walk(node->right);
         }
}

        中序的非递归遍历： 左----根----右
        由上面的递归信息了解到，中序的中序遍历首先访问的最左侧最喜下边的节点。
        因此可以使用循环一直向左子树的左孩子遍历，由于要对访问过的节点对右孩子进行访问，因此使用栈将方法访问的节点全部记录 。找到最左侧之后。出栈--------》访问 -----（将出栈的每个结点看作只有右子树的节点）-------遍历右子树------（将右结点看作一个新的二叉树又重复上面的工作--------循环；
       

void Fdg_walk(BTree *node)
{
  for(;;) {
       while(node)<=======================>if(node):考虑到时间的复杂度两者是等价的。
       {
         PUSH(stack,*node);
          node = node->left;
        }
        访问；
         POP(stack,node);
        node = node->right;
        if( isStackEmpty(stack) == TRUE)
             return ;
    }
}

static void destroy(struct BTree *node)
{
            if(node == NULL)
                      return ;
            destroy(node->left);
            destroy(node->right);
           free(node);
}

如果是含有父节点指针的结构体，那么就不需要栈了 。
穿线-----》记录前趋和后继；


使用二叉树构建哈夫曼的压缩和相应的解压缩 ；

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

#define    MAX                            128
struct NODE {
    char ch;
    int fre;
    int parent;
    int Lchild;
    int Rchild;
    char *code;
};
struct MESS {
    int total;
    struct NODE * static_link;
};

int getString(struct MESS*,char**);
void fillMessage(struct MESS*, int *,int);
void creatTree(struct MESS *);
int findSmall(struct MESS);
void makeCode(struct MESS *);
char * haFuMa(struct MESS, char *);
void unHaFuMa(struct MESS,char *);
void unHaFuMa(struct MESS mess,char *code)
{
  int                        index = mess.total-1,in=0;
  char                        st[80];
  printf("please input the string\n");
  gets(st);
  while(st[in])
  {
      if(mess.static_link[index].ch=='#')
      {
          if(st[in]=='0')
          index = mess.static_link[index].Lchild;
        else
              index = mess.static_link[index].Rchild;
          in++;
      }
      else
      {
          printf("%c",mess.static_link[index].ch);
          index = mess.total-1;
      }
  }
  if(mess.static_link[index].
      printf("%c\n",mess.static_link[index].ch);
  else
      printf("\nhas wrong\n");
}
char * haFuMa(struct MESS mess, char*st)
{
    int                    index = 0;
    char                *code = (char *)malloc(sizeof(char)*300);
    printf("%d \n",mess.total);
    for(index = 0; index <(mess.total); index++)
        printf("%c %d %d %d %d %s\n",mess.static_link[index].ch,mess.static_link[index].fre,mess.static_link[index].parent,mess.static_link[index].Lchild,mess.static_link[index].Rchild,mess.static_link[index].code);
    printf("\n******************************************************************************\n");
    while(*st) {
    for(index = 0; index <(mess.total+1)/2&&mess.static_link[index].ch!=*st; index++)
                ;
    if(mess.static_link[index].ch==*st)
        strcat(code,mess.static_link[index].code);
    st++;
    }
    return code;
}
void  makeCode(struct MESS *mess)
{
    int                            index = 0,in ,n,count, ij =0;
    char                        code[(mess->total+1)/2+1];

    code[(mess->total+1)/2] = 0;
    for(index = 0; index <( mess->total+1)/2; index++) {
        count = (mess->total+1)/2-1;
        ij =0;
        in = mess->static_link[index].parent;
        n = index;
        while(in>=0) {
        if(mess->static_link[in].Lchild == n)
            code[count--] = '0';
        else
            code[count--] = '1';
        n = in;
        in = mess->static_link[in].parent ;
        ij++;
        }
        strcpy(mess->static_link[index].code,code+count+1);
    }
}
int findSmall(struct MESS mess)
{
    int                index = 0,count = -1;

    for(index =0;index<mess.total;index++)
    {
        if(mess.static_link[index].parent==-1) {
            if(count==-1)
                count = index;
         if(mess.static_link[index].fre<mess.static_link[count].fre)
             count = index;
        }
    }
    return count;
}
void fillMessage(struct MESS*mess, int *ch, int total)
{
    int                                count = 0,index=0;
    int                                il = -1,ir = -1;
    mess->total = total;
    mess->static_link = (struct NODE *)malloc((2*total-1)*sizeof(struct NODE));
    for(count = 0; count < MAX; count++)
        if(ch[count]!=0) {
            mess->static_link[index].ch = count;
            mess->static_link[index].fre = ch[count];
            mess->static_link[index].Rchild = mess->static_link[index].Lchild = mess->static_link[index].parent = -1;
            mess->static_link[index++].code = (char *)malloc(total*sizeof(char));
        }
    while(mess->total < 2*total-1&&(il = findSmall(*mess))!=-1)
        {
            mess->static_link[il].parent = index;
            ir = findSmall(*mess);
            if(ir !=-1) {
                mess->static_link[index].ch ='#';
                mess->static_link[index].fre = mess->static_link[ir].fre+mess->static_link[il].fre;
                mess->static_link[index].Rchild=ir;
                mess->static_link[index].Lchild = il;
                mess->static_link[ir].parent= index;
                   mess->static_link[index].parent = -1;
                mess->static_link[index++].code = NULL;
                mess->total++;
        }
    }
}
int getString(struct MESS *mess, char **st)
{
    char                               *string;
    int                                  index,count = 0, in = 0, ch[MAX] = {0};

    string = (char*)malloc(sizeof(char)*MAX);
    printf("please input the complier string\n");
    count = read(0,string,MAX);
    for(index =0 ; index < count-1; index++) {
        if(ch[*(string+index)]==0)
            in++;
        ch[*(string+index)]++;
    }
    fillMessage(mess,ch,in);
    makeCode(mess);
    *st=haFuMa(*mess,string);
    free(string);
}
int main()
{
    struct MESS                            mess = {0,NULL};
    char                                 *code;
    getString(&mess,&code);
    puts(code);
    unHaFuMa(mess,code);
}