哈夫曼树的构造算法以及计算加权路径长度WPL

Dear 丶 2023-05-21 11:54 26阅读 0赞

# 哈夫曼树的构造算法 #

## 算法思路 ##

有W1,W2… …W1 一共n个权值的结点，把每个结点看作一棵树。

1.  从n个结点中找出权值最小的两个结点，创建一个新结点，权值为二者的和。
2.  两个结点分别为新结点的左右孩子（左小右大，左大右小都可以）。
3.  将两个结点从森林中删除，新结点加入其中
4.  重复1 ~ 3步，直至只剩一棵树，这棵树便是哈夫曼树。

如何用一个数组来构建一棵树？如 arr = \{3,4,2,5,7,2\}

可以发现第二步中每次是取树中权值最小的两个，用完以后需要删除，并且新结点加入，新结点的大小未知。

满足动态的删增需求，元素之间是简单的线性关系，所以采用链表的存储结构来存储这些树的结点。

这个链表应该时刻保持有序，每次从表中删除最小的两个结点，时间复杂度是O(1)，插入新结点的时候要保持链表有序，时间复杂度是O(n);

下面是C语言算法实现：

//链表结点的结构
     typedef struct LinkNode{ 
         SearchTree  tree;
         struct LinkNode * next;
     }LinkNode,*LinkList;
     //链表（含头结点）的删除方法，每次删除第一个非头结点的结点
     LinkNode * pop(LinkList list){ 
         LinkNode * result = nullptr;
         if(list->next)result = list->next;
         list->next = list->next->next;
         return result;
     }
     //插入的时候保持链表有序
    void * push(LinkList list,SearchTree tree){ 
         auto node = (LinkList)malloc(sizeof(LinkList));
         node->tree = tree;
         while(list->next){ 
             if(list->next->tree->data >= tree->data)break;
             else list = list->next;
         }
         node->next = list->next;
         list->next = node;
     }
    //生成哈夫曼树的主函数
     SearchNode * GreateHFM(const int * arr,int length){ 
         if(length < 1)return nullptr;//数组长度小于1返回空
         auto head = (LinkList)malloc(sizeof(LinkNode));//首先创建头结点
         head->next = nullptr;
         //遍历权值数组，每一个权值对应一个树结点
         for (int i = 0; i < length;i++) { 
             auto tree = (SearchTree)malloc(sizeof(SearchNode));
             tree->data = arr[i];
             tree->left = tree->right = nullptr;
             push(head,tree);//将其加入到有序链表中
         }
         //n个结点要循环n - 1次
         for(int i = 0;i < length - 1;i++){ 
             LinkNode* tree1 = pop(head);
             LinkNode* tree2 = pop(head); //弹出了两个最小的结点
             
             auto * father = (SearchTree)malloc(sizeof(SearchNode)); //二者权值之和的结点
             father->data = tree1->tree->data + tree2->tree->data;
             father->left = tree1->tree;
             father->right = tree2->tree;
                push(head,father);//将新结点加入到链表中
         }
         return head->next->tree;//最后将哈夫曼树返回
     }

# 计算哈夫曼树的带权路径长度 #

如何计算每个叶结点到根结点的路径长度？只有知道路径长度才能计算带权路径长度

方法有很多，这里采用后序遍历的非递归算法来实现。  
如果不懂后序遍历的非递归算法，可以参考下面这个博文的对应内容：  
[二叉树遍历全面总结（先，中，后序，层序，递归及非递归版本，如何利用遍历方法解决实际问题）][Link 1]

int compute_WPL(SearchTree tree){ 
         if(tree == nullptr)return 0;//当树为空的时候返回0
         stack<SearchTree >helper;//辅助栈，用于后序遍历
         int wpl = 0; //最后要返回的带权路径长度之和
         int height = 0;//表示当前结点对应的层级
         SearchNode * pre = nullptr;
         while(tree || !helper.empty()){ 
             if(tree){ 
                 helper.push(tree);
                 height++;
                 tree = tree->left;
             }else{ 
                 tree = helper.top();
                 if(tree->right && (!pre || pre != tree->right)){ 
                     tree = tree->right;
                 }else{ 
                     if(!tree->right)wpl += (height - 1) * tree->data;//只有是叶结点的时候才计算带权路径长度
                     helper.pop();
                     height--;
                     pre = tree;
                     tree = nullptr;
                 }
             }
         }
         return wpl;
     }

[Link 1]: https://blog.csdn.net/qq_43152622/article/details/105457382