【数据结构】中的哈弗曼树-HuffmanTree

我不是女神ヾ 2022-06-18 09:12 158阅读 0赞

概念：

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

基本术语：

哈夫曼树（霍夫曼树）又称为最优树.

1，路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长

度为L-1。

2、结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

3、树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

代码实现：

head.h

#include<iostream>
    using namespace std;
    #include<vector> 
    template<typename T>
    class Heap
    {
    public:
    	Heap()
    	{}
    
    
    	Heap(T arr[], size_t n)
    		:_a(arr, arr + n)
    	{
    		//构建堆，需要先将子树先构建成堆 
    		for (int i = (_a.size() - 2) / 2; i >= 0; i--)
    		{
    			//向下调整使该树成为堆 
    			_AdjustDown(i);
    		}
    	}
    
    
    	void Pop()
    	{
    		//将根节点的值和最后一个值进行交换，再将最后一个元素不视为堆内的元素，进行向下调整 
    		swap(_a[0], _a[_a.size() - 1]);
    		_a.pop_back();
    		_AdjustDown(0);
    	}
    
    
    	void Push(const T& x)
    	{
    		_a.push_back(x);
    		_AdjustUp(_a.size() - 1);
    	}
    protected:
    	vector<T> _a;
    protected:
    	//插入一个节点，该节点的加入可能破坏了堆的结构 
    	//向上调整是使加入节点后的树继续满足堆的条件 
    	void _AdjustUp(int i)
    	{
    		int child = i;
    		int parent = (i - 1) / 2;
    
    
    		//当子节点没有达到堆顶 
    		while (child >= 0)
    		{
    			//如果子比父亲大，则交换。并且进行下一轮的判断 
    			if (_a[child]>_a[parent])
    			{
    				swap(_a[child], _a[parent]);
    				child = parent;
    				parent = (parent - 1) / 2;
    			}
    			else//不用交换堆，直接结束 
    			{
    				break;
    			}
    		}
    	}
    
    
    	//向下调整 
    	//在构建堆时，或者堆顶元素被pop时，需要向下调整 
    	//1、构建堆，先将最小的子树构建成堆，慢慢将堆生长 
    	//2、pop后，堆顶元素不满足堆的情况，但是其他子树是满足堆的，所以只需对堆顶元素向下调整 
    	void _AdjustDown(int root)
    	{
    		int parent = root;
    		int child = 2 * parent + 1;
    
    
    		//child不能大于节点总的个数 
    		while (child<_a.size())
    		{
    			//如果右节点存在并且比左边节点大 
    			if (child + 1 < _a.size() && _a[child + 1] > _a[child])
    			{
    				child++;
    			}
    
    
    			//如果孩子比父亲大,则交换，进行下一次循环 
    			//否则，跳出循环 
    			if (_a[child] > _a[parent])
    			{
    				swap(_a[child], _a[parent]);
    				//父亲孩子向下走 
    				parent = child;
    				child = child * 2 + 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    };

HuffmanTree.h

#pragma once
    #include<iostream>
    using namespace std;
    #include<vector>
    #include"head.h"
    
    
    template<typename T>
    struct HuffmanTreeNode
    {
    	typedef HuffmanTreeNode<T> Node;
    
    
    	T _weight;
    
    	HuffmanTreeNode<T>* _left;
    	HuffmanTreeNode<T>* _right;
    	HuffmanTreeNode<T>* _parent;
    
    	HuffmanTreeNode(const T& x)
    		:_left(0)
    		, _right(0)
    		, _parent(0)
    		, _weight(x)
    	{
    	}
    };
    
    template<typename T>
    
    class HuffmanTree
    {
    	typedef HuffmanTreeNode<T> Node;
    
    public:
    	HuffmanTree()
    	{}
    
    	HuffmanTree(T* arr, size_t n, T& invalid)
    	{
    		struct compare
    		{
    			bool operator()(Node* l, Node* r)
    			{
    				return l->_weight < r->_weight;
    			}
    		};
    
    		Heap <Node*, compare> hp;
    		for (size_t i = 0; i<n; ++i)
    		{
    			if (arr[i] != invalid)
    			{
    				hp.Push(new Node(arr[i]));
    			}
    		}
    
    		while (hp.Size()>1)
    		{
    			Node* left = hp.Top();
    			hp.Pop();
    			Node* right = hp.Top();
    			hp.Pop();
    			Node* parent = new Node(left->_weight + right->_weight);
    
    			parent->_left = left;
    			parent->_right = right;
    			left->_parent = parent;
    			right->_parent = parent;
    			hp.Push(parent);
    		}
    		_root = hp.Top();
    	}
    
    	~HuffmanTree()
    	{
    		Destory(_root);
    		_root(NULL);
    	}
    
    protected:
    	Node* _root;
    
    	void Destory(Node* root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    
    		Destory(root->_left);
    		Destory(root->_right);
    
    		deleet root;
    		root = NULL;
    	}
    
    	HuffmanTree(const HuffmanTree<T>& t);
    	HuffmanTree& operator=(const HuffmanTree<T>& t);
    };