用一段C语言实现(1) 输入字符序列,建立二叉链表。 (2) 中序遍历二叉树:递归算法。 (3)中序遍历二叉树:非递归算法。 (4)求二叉树的高度 。 (5)为N个权值设计哈夫曼编码。
时间: 2024-01-13 10:03:40 浏览: 22
好的,我会根据您的要求来回答问题,下面是用C语言实现的代码:
1. 输入字符序列,建立二叉链表
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
TreeNode* createTree() {
char ch;
scanf("%c", &ch);
if (ch == '#') { // 如果读入的字符是 # 则表示该节点为空
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = ch;
root->left = createTree();
root->right = createTree();
return root;
}
```
2. 中序遍历二叉树:递归算法
```c
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%c ", root->data);
inorderTraversal(root->right);
}
```
3. 中序遍历二叉树:非递归算法
```c
typedef struct StackNode {
TreeNode* tree;
struct StackNode* next;
} StackNode;
typedef struct Stack {
StackNode* top;
int size;
} Stack;
Stack* createStack() {
Stack* stack = (Stack*)malloc(sizeof(Stack));
stack->top = NULL;
stack->size = 0;
return stack;
}
void push(Stack* stack, TreeNode* tree) {
StackNode* node = (StackNode*)malloc(sizeof(StackNode));
node->tree = tree;
node->next = stack->top;
stack->top = node;
stack->size++;
}
TreeNode* pop(Stack* stack) {
if (stack->size == 0) {
return NULL;
}
TreeNode* tree = stack->top->tree;
StackNode* temp = stack->top;
stack->top = stack->top->next;
stack->size--;
free(temp);
return tree;
}
void inorderTraversal(TreeNode* root) {
Stack* stack = createStack();
TreeNode* p = root;
while (p != NULL || stack->size != 0) {
while (p != NULL) {
push(stack, p);
p = p->left;
}
if (stack->size != 0) {
p = pop(stack);
printf("%c ", p->data);
p = p->right;
}
}
}
```
4. 求二叉树的高度
```c
int getHeight(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
```
5. 为N个权值设计哈夫曼编码
```c
#include <string.h>
typedef struct HuffNode {
int weight;
char code[100]; // 存放编码
struct HuffNode* left;
struct HuffNode* right;
} HuffNode;
void sort(HuffNode** a, int n) {
HuffNode* temp;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i]->weight > a[j]->weight) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
void createHuffTree(HuffNode** a, int n) {
for (int i = 1; i < n; i++) {
HuffNode* node = (HuffNode*)malloc(sizeof(HuffNode));
node->weight = a[0]->weight + a[1]->weight;
node->left = a[0];
node->right = a[1];
a[0] = node;
for (int j = 1; j < n - i; j++) {
a[j] = a[j + 1];
}
sort(a, n - i);
}
}
void huffCode(HuffNode* root, char* code) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) { // 叶子节点
strcpy(root->code, code);
return;
}
strcat(code, "0");
huffCode(root->left, code);
code[strlen(code) - 1] = '\0';
strcat(code, "1");
huffCode(root->right, code);
code[strlen(code) - 1] = '\0';
}
void printHuffCode(HuffNode** a, int n) {
for (int i = 0; i < n; i++) {
printf("%d %s\n", a[i]->weight, a[i]->code);
}
}
int main() {
int n;
scanf("%d", &n);
HuffNode** a = (HuffNode**)malloc(sizeof(HuffNode*) * n);
for (int i = 0; i < n; i++) {
a[i] = (HuffNode*)malloc(sizeof(HuffNode));
scanf("%d", &a[i]->weight);
a[i]->left = NULL;
a[i]->right = NULL;
}
sort(a, n);
createHuffTree(a, n);
char code[100] = "";
huffCode(a[0], code);
printHuffCode(a, n);
return 0;
}
```
以上是对您提出的问题的回答,希望能够帮到您!