哈夫曼树输出算法(递归横向输出)

Question

（2）哈夫曼树输出算法；
（提示：递归横向输出函数：void PrintBTNode(HuffNode *hf, int index,int n){）

Answer 1

该回答引用chatgpt:

#include<iostream>
using namespace std;

struct HuffNode{
    int weight; // 权值
    int parent; // 双亲结点下标
    int lchild; // 左孩子下标
    int rchild; // 右孩子下标
};

// 打印节点函数
void PrintBTNode(HuffNode *hf, int index,int n){
    // 若节点为空则返回
    if (hf == NULL) return;
    // 递归输出右子树
    PrintBTNode(hf, hf[index].rchild, n + 5);
    // 输出节点
    for (int i = 0; i < n; i++) cout << " ";
    cout << hf[index].weight << endl;
    // 递归输出左子树
    PrintBTNode(hf, hf[index].lchild, n + 5);
}

int main(){
    // 创建哈夫曼树
    HuffNode huffman[6] = {{5,-1,-1,-1},{6,-1,-1,-1},{8,-1,-1,-1},{9,-1,-1,-1},{11,-1,-1,-1},{14,-1,-1,-1}};
    for(int i=0;i<5;i++){
        int min1=100,min2=100;
        int j1=0,j2=0;
        for(int j=0;j<6+i;j++){
            if(huffman[j].weight<min1&&huffman[j].parent==-1){
                min2=min1;
                j2=j1;
                min1=huffman[j].weight;
                j1=j;
            }else if(huffman[j].weight<min2&&huffman[j].parent==-1){
                min2=huffman[j].weight;
                j2=j;
            }
        }
        huffman[j1].parent=huffman[j2].parent=5+i;
        huffman[5+i].weight=huffman[j1].weight+huffman[j2].weight;
        huffman[5+i].lchild=j1;
        huffman[5+i].rchild=j2;
    }
    // 输出哈夫曼树
    cout << "Huffman Tree:" << endl;
    PrintBTNode(huffman, 10, 0);
    return 0;
}
Huffman Tree:
                       53
               27
                       26
       14
                       12
               11
                       10
   5
                       4
               3
                       2