如何横向输出哈夫曼树

哈夫曼树是一种二叉树，可以采用层序遍历的方式进行横向输出。具体实现方法如下：
1. 首先将根节点入队列；
2. 在队列不为空的情况下，依次出队列；
3. 将出队列节点的左右子节点入队列；
4. 每一层的节点之间可以用空格或者其他符号分隔开。

下面是一个示例代码：

def level_order_traversal(root):
    if not root:
        return
    queue = [root]
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.pop(0)
            level.append(str(node.val))
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        print(" ".join(level))

其中，root表示哈夫曼树的根节点。函数中，首先将根节点加入队列中。然后，在队列不为空的情况下，依次取出队首节点，并将其左右子节点加入队列中。最后，将该层节点的值输出，并用空格隔开。这样就可以实现哈夫曼树的横向输出了。

相关问题

c语言横向输出哈夫曼树

首先需要构建一棵哈夫曼树，然后进行横向输出。以下是C语言代码示例：

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

#define MAX_SIZE 100

// 定义哈夫曼树结点
typedef struct {
    int weight;     // 权值
    int parent;     // 双亲结点下标
    int leftChild;  // 左孩子结点下标
    int rightChild; // 右孩子结点下标
} HTNode, *HuffmanTree;

// 构造哈夫曼树
void createHuffmanTree(HuffmanTree HT, int n) {
    int i, j;
    // 初始化哈夫曼树
    for(i = 0; i < 2 * n - 1; i++) {
        HT[i].parent = -1;
        HT[i].leftChild = -1;
        HT[i].rightChild = -1;
    }
    // 输入每个叶子结点的权值
    for(i = 0; i < n; i++) {
        printf("请输入第%d个叶子结点的权值：", i+1);
        scanf("%d", &HT[i].weight);
    }
    // 构建哈夫曼树
    for(i = n; i < 2 * n - 1; i++) {
        int min1 = MAX_SIZE, min2 = MAX_SIZE;
        int left = -1, right = -1;
        // 找出权值最小的两个结点
        for(j = 0; j < i; j++) {
            if(HT[j].parent == -1) {
                if(HT[j].weight < min1) {
                    min2 = min1;
                    right = left;
                    min1 = HT[j].weight;
                    left = j;
                } else if(HT[j].weight < min2) {
                    min2 = HT[j].weight;
                    right = j;
                }
            }
        }
        // 合并成新的结点
        HT[i].weight = HT[left].weight + HT[right].weight;
        HT[i].leftChild = left;
        HT[i].rightChild = right;
        HT[left].parent = i;
        HT[right].parent = i;
    }
}

// 横向输出哈夫曼树
void printHuffmanTree(HuffmanTree HT, int n) {
    int i, j, k;
    for(i = 0; i < n; i++) {
        printf("%d: ", i);
        for(j = 0; j < HT[i].weight; j++) {
            printf("*");
        }
        printf("\n");
        k = HT[i].parent;
        while(k != -1) {
            if(i == HT[k].leftChild) {
                printf("│ ");
            } else {
                printf(" ");
            }
            k = HT[k].parent;
        }
    }
}

int main() {
    HuffmanTree HT;
    int n;
    printf("请输入叶子结点的个数：");
    scanf("%d", &n);
    // 动态分配哈夫曼树结点
    HT = (HuffmanTree)malloc(sizeof(HTNode) * (2 * n - 1));
    createHuffmanTree(HT, n);
    printHuffmanTree(HT, n);
    free(HT);
    return 0;
}

这段代码中，首先定义了哈夫曼树结点的结构体HTNode和指向结点的指针HuffmanTree。然后定义了函数createHuffmanTree用于构造哈夫曼树，输入每个叶子结点的权值，计算出每个结点的权值和父子关系。接着定义了函数printHuffmanTree用于横向输出哈夫曼树，输出每个结点的权值和对应数量的星号，并且根据父子关系输出水平线和竖直线。最后在主函数中动态分配哈夫曼树结点、调用创建函数和输出函数、释放内存。

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

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

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 + '    ')

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