C语言用队列函数的形式实现哈夫曼树的层次遍历,并输出所有叶子结点到根结点的路径序列,用代码显示出来
时间: 2024-05-19 11:13:52 浏览: 15
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODE_NUM 100
typedef struct TreeNode {
int weight; // 权值
int parent; // 父节点在数组中的下标
int left; // 左子节点在数组中的下标
int right; // 右子节点在数组中的下标
} TreeNode;
typedef struct {
int front;
int rear;
TreeNode data[MAX_NODE_NUM];
} Queue;
void initQueue(Queue *q) {
q->front = q->rear = 0;
}
int isQueueEmpty(Queue *q) {
return q->front == q->rear;
}
int isQueueFull(Queue *q) {
return (q->rear + 1) % MAX_NODE_NUM == q->front;
}
void enQueue(Queue *q, TreeNode node) {
if (isQueueFull(q)) {
printf("Queue is full.\n");
exit(1);
}
q->data[q->rear] = node;
q->rear = (q->rear + 1) % MAX_NODE_NUM;
}
TreeNode deQueue(Queue *q) {
if (isQueueEmpty(q)) {
printf("Queue is empty.\n");
exit(1);
}
TreeNode node = q->data[q->front];
q->front = (q->front + 1) % MAX_NODE_NUM;
return node;
}
void printPath(TreeNode *tree, int index) {
int stack[MAX_NODE_NUM];
int top = -1;
while (index != -1) {
stack[++top] = index;
index = tree[index].parent;
}
while (top >= 0) {
printf("%d ", tree[stack[top]].weight);
top--;
}
printf("\n");
}
void huffmanTreeLevelOrder(TreeNode *tree, int n) {
if (n <= 0) {
return;
}
Queue q;
initQueue(&q);
for (int i = 0; i < n; i++) {
enQueue(&q, tree[i]);
}
while (!isQueueEmpty(&q)) {
int size = (q.rear - q.front + MAX_NODE_NUM) % MAX_NODE_NUM;
for (int i = 0; i < size; i++) {
TreeNode node = deQueue(&q);
if (node.left == -1 && node.right == -1) {
printPath(tree, node.parent);
}
if (node.left != -1) {
enQueue(&q, tree[node.left]);
}
if (node.right != -1) {
enQueue(&q, tree[node.right]);
}
}
}
}
int main() {
int n;
printf("Enter the number of leaf nodes: ");
scanf("%d", &n);
TreeNode tree[MAX_NODE_NUM * 2 - 1];
for (int i = 0; i < n; i++) {
printf("Enter the weight of node %d: ", i);
scanf("%d", &tree[i].weight);
tree[i].parent = -1;
tree[i].left = -1;
tree[i].right = -1;
}
for (int i = n; i < 2 * n - 1; i++) {
tree[i].weight = 0;
tree[i].parent = -1;
tree[i].left = -1;
tree[i].right = -1;
}
for (int i = n; i < 2 * n - 1; i++) {
int min1 = -1, min2 = -1;
for (int j = 0; j < i; j++) {
if (tree[j].parent == -1) {
if (min1 == -1 || tree[j].weight < tree[min1].weight) {
min2 = min1;
min1 = j;
} else if (min2 == -1 || tree[j].weight < tree[min2].weight) {
min2 = j;
}
}
}
tree[i].weight = tree[min1].weight + tree[min2].weight;
tree[i].left = min1;
tree[i].right = min2;
tree[min1].parent = i;
tree[min2].parent = i;
}
printf("The path from leaf nodes to root node:\n");
huffmanTreeLevelOrder(tree, 2 * n - 1);
return 0;
}