数据结构-哈夫曼树（未完成）

              1 #include"stdio.h"  2 #include"stdlib.h"  3//定义哈夫曼节点类型  4 typedef struct node{
  5int weight; //权值  6struct node *left;  //左孩子  7struct node *right;  //右孩子  8struct node *next;  //下一个节点  9}Huffman;
 10//初始化哈夫曼 11 Huffman* creatHuffman()
 12{
 13int n;
 14     Huffman *h; 
 15     Huffman *p;
 16     Huffman *q;
 17     h = q = (Huffman*)malloc(sizeof(Huffman));
 18     printf("请输入您需要几个节点：");
 19     scanf("%d",&n);
 20if(n <= 0 )
 21    {
 22         printf("您输入的数值有错误！");
 23return NULL;
 24    }
 25else 26    {
 27for( int i = 0; i < n; i++)
 28        {
 29             p = (Huffman*)malloc(sizeof(Huffman));
 30             printf("请输入第%d个节点的值：",i+1);
 31             scanf("%d",&p->weight);
 32             p->left = NULL;
 33             p->right = NULL;
 34             q->next = p;
 35        }
 36         p->next = NULL;
 37//返回h的下一个节点，h是哈夫曼节点链表的头结点,这里直接返回有值的节点就可以了； 38return h->next;
 39    }
 40}
 41//删除节点 42void delNode(Huffman *h, int index)
 43{
 44     Huffman *p = h;
 45     Huffman *q;
 46if(index = 0)
 47    {
 48         h = h->next;
 49return;
 50    }
 51for(int i = 0; i < index - 1; i++)  //移动到要删除的节点的前一个 52    {
 53         p = p->next;
 54    }
 55     q = p;  //将q指向p的前一个节点 56     p = p->next;    //p移动到了要删除的节点 57     q->next = p->next;  //链表中该元素消除 58}
 59//合并两个节点，成为一个新的节点，并将两个节点作为该节点的左右孩子 60void mergeNode(Huffman *h ,Huffman *min1, Huffman *min2)
 61{
 62     Huffman *newNode =(Huffman*)malloc(sizeof(Huffman));    //建立新的节点 63     Huffman *p = h;
 64     newNode->weight = min1->weight + min2->weight;  //合并两个节点的权值赋值给合并的节点 65     newNode->left = min1;
 66     newNode->right = min2; 
 67while(p->next != NULL)
 68    {
 69         p = p->next;
 70    }
 71     p->next = newNode;  //将新节点放入节点链表的最后一个，以便于后面比较大小 72     newNode->next = NULL;
 73}
 74//比较大小,找出两个最小的值的节点 75void compareNode(Huffman *h)
 76{
 77//退出递归条件，当这个节点链表只剩最后一个节点（根节点）时退出 78if(h->next == NULL)
 79    {
 80return ;
 81    }
 82int index = 0;  //标记最小值的位置 83int count = 0;  //标记当前在第几个节点 84     Huffman *min1,*min2;
 85     Huffman *p = h;
 86     min1 = h;
 87     p = h->next;
 88//寻找最小值 89while(p != NULL)
 90    {
 91         count++;
 92if(p->weight < min1->weight)
 93        {
 94             min1 = p;
 95             index = count;
 96        }
 97         p = p->next;
 98    }
 99     delNode(h, index);  //调用删除节点函数删除链表中的该节点100     count = 0;  //节点重头开始101     p = h->next;
102     min2 = h;
103//寻找第二个最小值104while(p != NULL)
105    {
106         count++;
107if(p->weight < min2->weight)
108        {
109             min2 = p;
110             index = count;
111        }
112         p = p->next;
113    }
114     delNode(h, index);//调用删除节点函数删除链表中的该节点115     compareNode(h);//递归调用自己116}
117//输出二叉树118void printTree(Huffman *h)
119{
120     printf("%d  ",h->weight);
121     printTree(h->left);
122     printTree(h->right);   
123}
124main()
125{
126     Huffman *h;
127     h = creatHuffman();
128    compareNode(h);
129    printTree(h);
130 }