编辑代码

#include <stdio.h>
#include "windows.h"


typedef char E;

struct Tree{
    E element;
    struct Tree * right;
    struct Tree * left;
    int value;
};

typedef struct Tree * tree;
typedef tree T;

struct LNode {
    T element;
    struct LNode *Next;
};

typedef struct LNode *Node;

struct Queue {
    Node front, rear;
};

typedef struct Queue *LQueue;

BOOL initQueue(LQueue queue) {
    queue->front = queue->rear = malloc(sizeof(struct LNode));
    if (queue->front == NULL) return 0;
    return 1;
}

// 链表队push方法
BOOL pushQueue(LQueue queue, T element) {
    Node NewNode = malloc(sizeof(struct LNode));    //  申请Node空间
    if (NewNode == NULL) return 0;  //空间不足返回Null
    NewNode->element = element;
    NewNode->Next = NULL;
    Node pre = queue->front;
    while (pre->Next && pre->Next->element->value <= element->value)
        pre = pre->Next;
    if (pre == queue->rear) {
        queue->rear->Next = NewNode;
        queue->rear = NewNode;
    } else {
        NewNode->Next = pre->Next;
        pre->Next = NewNode;
    }
    return 1;
}

// 判断链表队是否为空
BOOL isEmpty(LQueue queue) {
    return queue->rear == queue->front;
}

T popQueue(LQueue queue) {
    if (isEmpty(queue)) return NULL; //判断队是否空，队空则返回-1
    queue->front = queue->front->Next;
    return queue->front->element;
}

tree createNode(E elemet,int value){
    tree node = malloc(sizeof (struct Tree));
    node->left=node->right=NULL;
    node->element = elemet;
    node->value = value;
    return node;
}

tree f(tree root){
    if (root == NULL) return NULL;
    printf("%c",root->element);
    f(root->left);
    f(root->right);
}

//遍历方法
void fq(LQueue queue) {
    printf(">>>");
    Node tmp = queue->front;
    do {
        if (isEmpty(queue)) {       //判断队是否为空，为空则不进行遍历，强行遍历会发生错误，不存在的node会随机指向一个Node
            printf("队为空<<<\n");
            return;
        }
        queue->front = queue->front->Next;
        printf("%c ", queue->front->element->element);
    } while (queue->front != queue->rear);
    queue->front = tmp;
    printf("<<<\n");
}

// 编码方法 哈夫曼编码
char * encode(tree root,E e){
    if (root == NULL ) return NULL;     // 找到最后，找不到返回Null
    if (root->element == e) return "";         // 找到返回空字符串
    char * str = encode(root->left,e);      // 先向左找
    char * s = malloc(sizeof (char)*10);
    if (str != NULL){           // 如果找到，则前一个会返回“ ”，则会执行这个if，反之返回Null，则跳到下一个分支
        s[0] = '0';
        str = strcat(s,str);
    }else{          // 左分支找不到，找右边
        str = encode(root->right,e);
        if (str != NULL){
            s[0] = '1';
            str = strcat(s,str);
        }
    }
    return str;     //最后返回 str
}

void printCode(tree root, E e){
    printf("%c的哈夫曼编码：%s", e,encode(root,'A'));
    printf("\n");
}
int main() {
    struct Queue queue;
    initQueue(&queue);

    pushQueue(&queue, createNode('A',5));
    pushQueue(&queue, createNode('B',16));
    pushQueue(&queue, createNode('C',8));
    pushQueue(&queue, createNode('D',13));

    fq(&queue);

    while (queue.front->Next != queue.rear){
        tree left = popQueue(&queue);
        tree right = popQueue(&queue);
        tree node = createNode(' ',left->value+right->value);
        node->left = left;
        node->right = right;
        pushQueue(&queue,node);
    }
    tree root = popQueue(&queue);
//    f(root);
    printCode(root,'A');
    printCode(root,'B');
    printCode(root,'C');
    printCode(root,'D');
}