C++中哈夫曼树的定义、构造及其遍历

哈夫曼树是一种特殊的二叉树，它的叶子节点代表一个字符或符号，并且每个叶子节点都有一个权值。哈夫曼树的构造基于贪心算法，它的目标是通过选择最小的两个节点来合并节点，直到最终形成一个根节点的二叉树，同时保证该二叉树的带权路径长度最小。

构造哈夫曼树的具体步骤如下：

1. 首先将所有节点按照权值从小到大排序，并构造一颗只包含所有叶子节点的二叉树。

2. 选择权值最小的两个节点作为左右子节点构造一个新的二叉树，将它的根节点权值设为左右子节点权值之和。

3. 重复上述过程，直到所有节点都被合并到一颗哈夫曼树中。

哈夫曼树的遍历方式和普通二叉树类似，主要有前序遍历、中序遍历和后序遍历。具体的实现方式也与普通二叉树类似，只不过需要注意的是，由于哈夫曼树不一定是平衡二叉树，因此它的遍历时间复杂度可能不是 O(n)，而可能是 O(nlogn)。

下面是C++中哈夫曼树的构造和遍历代码示例：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 哈夫曼树节点
struct HuffmanNode {
    int weight;         // 权值
    int parent, left, right;    // 父节点、左子节点、右子节点

    HuffmanNode() : weight(0), parent(-1), left(-1), right(-1) {}
    HuffmanNode(int w) : weight(w), parent(-1), left(-1), right(-1) {}
};

// 构造哈夫曼树
void buildHuffmanTree(vector<int> weights, vector<HuffmanNode>& nodes) {
    priority_queue<int, vector<int>, greater<int>> pq;   // 小根堆

    // 初始化叶子节点
    int n = weights.size();
    for (int i = 0; i < n; i++) {
        nodes[i] = HuffmanNode(weights[i]);
        pq.push(i);
    }

    // 构造哈夫曼树
    while (pq.size() > 1) {
        int i = pq.top(); pq.pop();
        int j = pq.top(); pq.pop();
        nodes[i].parent = nodes[j].parent = pq.size();
        nodes[pq.size()] = HuffmanNode(nodes[i].weight + nodes[j].weight);
        nodes[pq.size()].left = i;
        nodes[pq.size()].right = j;
        pq.push(pq.size());
    }
}

// 前序遍历哈夫曼树

哈夫曼树遍历

哈夫曼树的遍历同样可以使用递归的方式来实现，遍历的顺序与二叉树一样有前序、中序和后序遍历。

1. 前序遍历

前序遍历的步骤与二叉树的前序遍历类似，先访问根节点，再遍历左子树和右子树。

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

1. 中序遍历

中序遍历同样与二叉树的中序遍历类似，先遍历左子树，再访问根节点，最后遍历右子树。

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

1. 后序遍历

后序遍历同样与二叉树的后序遍历类似，先遍历左子树，再遍历右子树，最后访问根节点。

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

需要注意的是，由于哈夫曼树是一棵完全二叉树，因此可以通过数组来表示。此时遍历的顺序就需要变换一下，具体来说，可以使用堆的性质进行遍历，具体实现可以参考以下代码。

void heapOrder(vector<TreeNode*>& tree) {
    if (tree.empty()) {
        return;
    }
    queue<TreeNode*> q;
    q.push(tree[0]);
    while (!q.empty()) {
        int n = q.size();
        for (int i = 0; i < n; ++i) {
            TreeNode* node = q.front();
            q.pop();
            cout << node->val << " ";
            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
    }
}

其中，tree 表示哈夫曼树，第一个节点为根节点，之后按照从上到下、从左到右的顺序存储其他节点。该函数中使用了一个队列 q 来实现遍历，每次取出队列中的第一个节点，输出该节点的值，然后将其左右孩子加入队列中。由于哈夫曼树是一棵完全二叉树，因此堆的性质也被满足，可以使用堆的遍历方式来实现哈夫曼树的遍历。

哈夫曼树是一种特殊的二叉树，它的构造方法是将权值最小的节点两两合并，形成一个新的节点，新节点的权值为两个被合并节点的权值之和。重复这个过程，直到所有节点都被合并成一个节点，这个节点就是哈夫曼树的根节点。

哈夫曼树的形态可以用类似下面的图形来表示：

               [50]
              /    \\
            /        \\
          /            \\
       [20]             [30]
        /  \\           /    \\
      /     \\         /      \\
    [10]    [10]     [15]     [15]
    /  \\     /  \\    /   \\    /   \\
  [5] [5]  [5] [5]  [7]  [8]  [7]  [8]

在这个例子中，数字表示节点的权值，方括号中的数字表示这个节点所代表的子树中所有节点的权值之和。最后合并成的根节点[50]表示整棵哈夫曼树的权值和。