哈夫曼树先序遍历

哈夫曼树的先序遍历是指从根节点开始，先输出根节点，然后先序遍历左子树，再先序遍历右子树。具体实现过程可以参考以下代码：

void preOrder(Node* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

其中，Node为哈夫曼树的节点类型，val为节点的权值。

相关问题

构造哈夫曼树，先序遍历哈夫曼树，计算WPL的值，打印哈夫曼树并释放哈夫曼树的C语言代码

哈夫曼树是一种带权路径长度最短的树，通常用于数据压缩。其构造方法如下：
1. 将所有权值看作一个森林，每个森林都是一个节点，节点的权值为森林中所有节点的权值之和。
2. 从森林中选取两个权值最小的节点组成一棵新树，其权值为这两个节点的权值之和。
3. 将新树插入森林中，并从森林中删除这两个节点。
4. 重复步骤2和步骤3，直到森林中只剩下一个树，即为哈夫曼树。

先序遍历哈夫曼树可以按照以下方式实现：
1. 先输出当前节点的权值。
2. 如果当前节点有左子树，则递归遍历左子树。
3. 如果当前节点有右子树，则递归遍历右子树。

计算WPL（带权路径长度）的值可以按照以下方式实现：
1. 对于每个叶子节点，将其权值乘以其到根节点的路径长度，得到该叶子节点的带权路径长度。
2. 将所有叶子节点的带权路径长度相加，得到WPL的值。

以下是打印哈夫曼树并释放哈夫曼树的C语言代码：

#include <stdio.h>
#include <stdlib.h>

// 哈夫曼树结点
typedef struct HuffmanNode {
    int weight;                     // 权值
    struct HuffmanNode *leftChild;  // 左孩子
    struct HuffmanNode *rightChild; // 右孩子
} HuffmanNode, *HuffmanTree;

// 构建哈夫曼树
void createHuffmanTree(HuffmanTree *tree, int weights[], int n) {
    if (n <= 0) {
        *tree = NULL;
        return;
    }
    // 创建森林
    HuffmanNode **forest = (HuffmanNode **)malloc(sizeof(HuffmanNode *) * n);
    for (int i = 0; i < n; i++) {
        forest[i] = (HuffmanNode *)malloc(sizeof(HuffmanNode));
        forest[i]->weight = weights[i];
        forest[i]->leftChild = NULL;
        forest[i]->rightChild = NULL;
    }
    while (n > 1) {
        // 找到最小的两个结点
        int min1 = 0, min2 = 1;
        if (forest[min1]->weight > forest[min2]->weight) {
            min1 = 1;
            min2 = 0;
        }
        for (int i = 2; i < n; i++) {
            if (forest[i]->weight < forest[min1]->weight) {
                min2 = min1;
                min1 = i;
            } else if (forest[i]->weight < forest[min2]->weight) {
                min2 = i;
            }
        }
        // 合并两个结点
        HuffmanNode *newNode = (HuffmanNode *)malloc(sizeof(HuffmanNode));
        newNode->weight = forest[min1]->weight + forest[min2]->weight;
        newNode->leftChild = forest[min1];
        newNode->rightChild = forest[min2];
        // 将新结点插入森林
        forest[min1] = newNode;
        for (int i = min2; i < n - 1; i++) {
            forest[i] = forest[i + 1];
        }
        n--;
    }
    *tree = forest;
    free(forest);
}

// 先序遍历哈夫曼树
void preorderTraversal(HuffmanTree tree) {
    if (tree != NULL) {
        printf("%d ", tree->weight);
        preorderTraversal(tree->leftChild);
        preorderTraversal(tree->rightChild);
    }
}

// 计算WPL的值
int getWPL(HuffmanTree tree, int depth) {
    if (tree == NULL) {
        return 0;
    } else if (tree->leftChild == NULL && tree->rightChild == NULL) {
        return tree->weight * depth;
    } else {
        return getWPL(tree->leftChild, depth + 1) + getWPL(tree->rightChild, depth + 1);
    }
}

// 打印哈夫曼树
void printHuffmanTree(HuffmanTree tree, int depth) {
    if (tree != NULL) {
        for (int i = 0; i < depth; i++) {
            printf("  ");
        }
        printf("%d\n", tree->weight);
        printHuffmanTree(tree->leftChild, depth + 1);
        printHuffmanTree(tree->rightChild, depth + 1);
    }
}

// 释放哈夫曼树
void destroyHuffmanTree(HuffmanTree tree) {
    if (tree != NULL) {
        destroyHuffmanTree(tree->leftChild);
        destroyHuffmanTree(tree->rightChild);
        free(tree);
    }
}

int main() {
    int weights[] = {3, 4, 5, 6, 7, 8};
    int n = sizeof(weights) / sizeof(int);
    HuffmanTree tree;
    createHuffmanTree(&tree, weights, n);
    printf("先序遍历哈夫曼树：");
    preorderTraversal(tree);
    printf("\n");
    int wpl = getWPL(tree, 0);
    printf("WPL的值：%d\n", wpl);
    printf("打印哈夫曼树：\n");
    printHuffmanTree(tree, 0);
    destroyHuffmanTree(tree);
    return 0;
}

编写一个用 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;
}

注意，由于哈夫曼树和哈夫曼编码需要使用到先前创建的二叉树或者额外输入数据，因此在菜单选择程序中需要进行一些变量的定义和修改，以保证程序正确运行。