二叉树(5)HuffmanTree

2020-02-19 16:00:40来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

二叉树(5)HuffmanTree

构建一棵 HuffmanTree。

 

测试代码 main.cpp:

#include <iostream>
#include "HuffmanTree.h"

using std::cout;
using std::endl;

int main()
{
    auto il = { 1,2,3,4,5,6,7,8,9 };

    HuffmanTree<int> ht(il.begin(), il.end());
    ht.levelTraversal();
    cout << endl;

    return 0;
}

 

头文件 "HuffmanTree.h":

#pragma once


#include <queue>

template<typename _Ty>
class HuffmanTree
{
    struct Node
    {
        _Ty weight;
        Node* left = nullptr;
        Node* right = nullptr;
        Node(const _Ty& _w) :weight(_w) {}
    };

public:
    HuffmanTree() = default;

    template<typename _Iter>
    HuffmanTree(_Iter _it1, _Iter _it2)
    {
        if (_it1 == _it2) return;
        std::priority_queue<Node*, std::vector<Node*>, comp> pq;
        while (_it1 != _it2)
        {
            Node* temp = new Node(*_it1);
            pq.push(temp);
            temp = nullptr;
            ++_it1;
        }
        while (true)
        {
            if (pq.size() == 1)
            {
                root = pq.top();
                return;
            }
            Node* temp = new Node(pq.top()->weight);
            temp->left = pq.top();
            pq.pop();
            temp->weight += pq.top()->weight;
            temp->right = pq.top();
            pq.pop();
            pq.push(temp);
            temp = nullptr;
        }
    }

    ~HuffmanTree() { clear(root); }

    void levelTraversal()
    {
        if (root == nullptr) return;
        std::queue<Node*> nodePointers;
        nodePointers.push(root);
        Node* cur = nullptr;
        while (!nodePointers.empty())
        {
            cur = nodePointers.front();
            std::cout << cur->weight << " ";
            if (cur->left != nullptr) nodePointers.push(cur->left);
            if (cur->right != nullptr) nodePointers.push(cur->right);
            nodePointers.pop();
        }
    }

    struct comp
    {
        bool operator ()(const Node* _n1, const Node* _n2) { return _n1->weight > _n2->weight; }
    };

private:
    void clear(Node*& _root)
    {
        if (_root == nullptr) return;
        clear(_root->left);
        clear(_root->right);
        delete _root;
        _root = nullptr;
    }

private:
    Node* root = nullptr;
};

 


原文链接:https://www.cnblogs.com/teternity/p/HuffmanTree.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:以八进制、十进制、十六进制、布尔值形式输出相关数

下一篇:序列归并