递归横向输出哈夫曼树函数

以下是递归横向输出哈夫曼树的函数实现：

def print_huffman_tree(node, prefix=''):
    """
    递归横向输出哈夫曼树
    :param node: 哈夫曼树结点
    :param prefix: 当前结点路径前缀
    """
    if node is None:
        return

    if node.left is None and node.right is None:
        # 叶子节点
        print(f'{prefix}└── {node.value}')
    else:
        # 非叶子节点
        print(f'{prefix}├── {node.value}')
        print_huffman_tree(node.left, prefix + '│   ')
        print_huffman_tree(node.right, prefix + '    ')

该函数会从根节点开始递归遍历哈夫曼树，横向输出每个结点的值，并在输出前加上当前结点在哈夫曼树中的路径前缀。对于叶子结点，输出格式为“路径前缀└── 值”，对于非叶子结点，输出格式为“路径前缀├── 值”。同时，为了使输出格式更加美观，还在路径前缀中添加了一些空格和竖线。

相关问题

怎么运用递归的思想横向输出哈夫曼树

哈夫曼树是一种特殊的二叉树，它的叶子节点代表着字符及其出现频率。通过构建哈夫曼树，可以得到一种高效的压缩编码方式。在横向输出哈夫曼树时，我们可以运用递归的思想来实现。

具体实现方法如下：
1. 首先，我们需要定义一个递归函数来遍历哈夫曼树。该函数的参数包括当前节点指针、节点深度、以及每层节点输出的缩进量。
2. 在递归函数中，首先输出当前节点的字符及其出现频率，并根据深度和缩进量输出该节点的位置。
3. 然后，递归处理当前节点的左子树和右子树。在处理左子树时，深度加1，缩进量增加一个固定值；在处理右子树时，深度加1，缩进量不变。
4. 当递归处理到叶子节点时，直接输出该节点的字符及其出现频率，并根据深度和缩进量输出该节点的位置。

下面是一个示例代码：

void printHuffmanTree(Node* root, int depth, int indent) {
    if (root == nullptr) {
        return;
    }
    // 输出当前节点的字符及其出现频率
    cout << root->ch << " (" << root->freq << ")" << endl;
    // 输出当前节点的位置
    for (int i = 0; i < indent; i++) {
        cout << " ";
    }
    cout << "|_" << endl;
    // 递归处理左子树
    printHuffmanTree(root->left, depth + 1, indent + 4);
    // 递归处理右子树
    printHuffmanTree(root->right, depth + 1, indent);
}

递归算法实现哈夫曼树横向输出

好的，下面是递归算法实现哈夫曼树横向输出的代码示例：

// 定义哈夫曼树结点
struct HNode {
    int weight;         // 权值
    int lchild, rchild; // 左孩子和右孩子在数组中的下标
};

// 按照权值从小到大排序
bool cmp(const HNode& a, const HNode& b) {
    return a.weight < b.weight;
}

// 递归构建哈夫曼树
int buildHT(HNode huffTree[], int n) {
    for (int i = 0; i < n; ++i) {
        huffTree[i].lchild = huffTree[i].rchild = -1;
    }
    for (int i = 0; i < n - 1; ++i) {
        // 找到权值最小的结点作为左孩子
        int min1 = min2 = 0;
        for (int j = 0; j < n; ++j) {
            if (huffTree[j].weight < huffTree[min1].weight) {
                min2 = min1;
                min1 = j;
            } else if (huffTree[j].weight < huffTree[min2].weight) {
                min2 = j;
            }
        }
        // 将找到的两个结点合并为一个新的结点
        huffTree[min1].weight += huffTree[min2].weight;
        huffTree[min1].lchild = min2;
        huffTree[min1].rchild = -1;
        huffTree[min2].rchild = min1;
    }
    return min1;    // 返回根结点在数组中的下标
}

// 层次遍历哈夫曼树并横向输出
void printHT(HNode huffTree[], int root, int depth) {
    if (root == -1) {
        return;
    }
    for (int i = 0; i < depth; ++i) {
        cout << "    ";
    }
    cout << huffTree[root].weight << endl;
    printHT(huffTree, huffTree[root].lchild, depth + 1);
    printHT(huffTree, huffTree[root].rchild, depth + 1);
}

其中，buildHT函数用于构建哈夫曼树，printHT函数用于层次遍历哈夫曼树并横向输出。在main函数中，先读入n个权值，然后构建哈夫曼树，最后调用printHT函数输出哈夫曼树。