编写一个用 C 语言实现一个菜单选择程序分别创建二叉树链表结构,并求出先序遍历和中序遍历的程序,同时也包含了构造哈夫曼树和哈夫曼编码
时间: 2024-02-18 15:05:50 浏览: 76
好的,以下是用 C 语言实现的菜单选择程序,包含创建二叉树链表结构、先序遍历和中序遍历的程序,以及构造哈夫曼树和哈夫曼编码。
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode *leftChild;
struct TreeNode *rightChild;
} TreeNode;
// 先序遍历
void preOrder(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%c ", root->data);
preOrder(root->leftChild);
preOrder(root->rightChild);
}
// 中序遍历
void inOrder(TreeNode *root) {
if (root == NULL) {
return;
}
inOrder(root->leftChild);
printf("%c ", root->data);
inOrder(root->rightChild);
}
// 创建二叉树
TreeNode* createBinaryTree() {
char ch;
scanf("%c", &ch);
if (ch == '#') {
return NULL;
}
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = ch;
root->leftChild = createBinaryTree();
root->rightChild = createBinaryTree();
return root;
}
// 哈夫曼树结点
typedef struct HuffmanNode {
int weight;
int parent;
int leftChild;
int rightChild;
} HuffmanNode;
// 选择两个权值最小的结点
void selectMinimum(HuffmanNode *nodes, int n, int *n1, int *n2) {
for (int i = 0; i < n; i++) {
if (nodes[i].parent == -1) {
*n1 = i;
break;
}
}
for (int i = 0; i < n; i++) {
if (nodes[i].parent == -1 && nodes[i].weight < nodes[*n1].weight) {
*n1 = i;
}
}
for (int i = 0; i < n; i++) {
if (nodes[i].parent == -1 && i != *n1) {
*n2 = i;
break;
}
}
for (int i = 0; i < n; i++) {
if (nodes[i].parent == -1 && nodes[i].weight < nodes[*n2].weight && i != *n1) {
*n2 = i;
}
}
}
// 构造哈夫曼树
void createHuffmanTree(HuffmanNode *nodes, int n) {
for (int i = 0; i < n - 1; i++) {
int n1, n2;
selectMinimum(nodes, i + 1, &n1, &n2);
nodes[n1].parent = i + n;
nodes[n2].parent = i + n;
nodes[i + n].weight = nodes[n1].weight + nodes[n2].weight;
nodes[i + n].leftChild = n1;
nodes[i + n].rightChild = n2;
}
}
// 哈夫曼编码
void huffmanCoding(HuffmanNode *nodes, int n) {
char **huffmanCode = (char**)malloc(n * sizeof(char*));
for (int i = 0; i < n; i++) {
huffmanCode[i] = (char*)malloc(n * sizeof(char));
huffmanCode[i][n - 1] = '\0';
int parent = nodes[i].parent;
int current = i;
int k = n - 2;
while (parent != -1) {
if (nodes[parent].leftChild == current) {
huffmanCode[i][k] = '0';
} else {
huffmanCode[i][k] = '1';
}
current = parent;
parent = nodes[current].parent;
k--;
}
printf("%c: %s\n", i + 'A', huffmanCode[i]);
}
}
int main() {
int choice;
do {
printf("1. 创建二叉树\n");
printf("2. 先序遍历\n");
printf("3. 中序遍历\n");
printf("4. 构造哈夫曼树\n");
printf("5. 哈夫曼编码\n");
printf("6. 退出\n");
printf("请选择操作:");
scanf("%d", &choice);
switch (choice) {
case 1: {
printf("请输入二叉树的先序遍历序列(#表示空结点):");
char ch;
scanf("%c", &ch);
TreeNode *root = createBinaryTree();
printf("二叉树创建成功!\n");
break;
}
case 2: {
printf("先序遍历:");
preOrder(root);
printf("\n");
break;
}
case 3: {
printf("中序遍历:");
inOrder(root);
printf("\n");
break;
}
case 4: {
int n;
printf("请输入哈夫曼树的叶子结点个数:");
scanf("%d", &n);
HuffmanNode *nodes = (HuffmanNode*)malloc((2 * n - 1) * sizeof(HuffmanNode));
for (int i = 0; i < n; i++) {
printf("请输入第%d个叶子结点的权值:", i + 1);
scanf("%d", &nodes[i].weight);
nodes[i].parent = -1;
nodes[i].leftChild = -1;
nodes[i].rightChild = -1;
}
createHuffmanTree(nodes, n);
printf("哈夫曼树构造成功!\n");
break;
}
case 5: {
huffmanCoding(nodes, n);
break;
}
}
} while (choice != 6);
return 0;
}
```
注意,由于哈夫曼树和哈夫曼编码需要使用到先前创建的二叉树或者额外输入数据,因此在菜单选择程序中需要进行一些变量的定义和修改,以保证程序正确运行。
阅读全文