霍夫曼树的详细C ++实现

霍夫曼树的结构在上面进行了分析:

机器学习关键人物: 如何在一篇文章中构造霍夫曼树？专栏.zhihu.com

以下是从C ++实现的角度分析构建霍夫曼树的过程. 首先，下面给出了创建霍夫曼树的完整步骤. 每个步骤的具体分析如下所示:

确定集合T元素（叶节点）的数量时，可以使用数组大小​​计算规则来确定数组的大小，因此可以使用静态数组来构造霍夫曼树. 霍夫曼树节点包括:

根据之前的分析，我们可以使用静态数组存储霍夫曼树. 以下是确定静态数组长度的过程:

（1）在构造霍夫曼树之前，存在n个树（叶节点）以形成集合T，且阵列度为n；

（2）每次合并仅涉及两棵树，就会生成一棵新树（需要向数组中添加元素），然后数组的长度需要为n + 1；

（3）每次合并后，集合T中的元素数量减少一（从T中删除参与合并的两棵树，并将新生成的树添加到T中）；

（4）构造完成后哈夫曼树结点，只有一棵树，即T仅具有一个元素，因此总共进行了n-1次构造，并生成了n-1棵新树，是，数组元素的数量从原始n变为n +（n-1）= 2n-1.

备注: 上面的每个“树”只需要一个节点即可存储，也就是说，只需要数组中的一个元素即可存储，即T中的每棵树都只需要存储其根节点.

根据先前的分析，节点类需要包含左右子节点，权重和父节点位置，其定义如下:

class Node {
public:
	int left, right;
    // -1表示无父节点
	int parent = -1;
	int weight = 0;
};

初始化数组中前n个树的根节点权重的函数如下:

void initLeafs(Node *p, int numLeafs) {
	// 对p指向的数组中前numLeafs个元素进行初始化
	for (int i = 0; i < numLeafs; i++) {
		int ch;
		cout << input :  << endl;
		cin >> ch;
		// 设置Node的权重
		p[i].weight = ch;
	}
	cout << --------------- << endl;
}

搜索权重最小的两个根节点时，需要确保该根节点没有父节点. 合并操作在根节点上执行，并且具有父节点的节点将不是树的根节点. 在所有已创建的根节点中搜索权重最小的两个节点的代码如下，可以将其视为顺序搜索算法:

void searchMin(const Node *p, int nums, int &min1, int &min2) {
	// 在p指向的nums个元素的数组中
	// 搜索权值最小的两个节点 
	// 并保证其parent为空，即根节点
	
	// 首先找到数组中第一个根节点，即parent为空的节点
	// 将此根节点作为weight最小节点，即采用排序算法
	for (int i = 0; i < nums; i++) {
		if (p[i].parent == -1) { 
			min1 = i;
			break;
		}
	}
	// 寻找数组中权值最小的根节点作为min1
	for (int i = 0; i < nums; i++) {
		if (p[i].parent == -1 && p[i].weight < p[min1].weight) {
			min1 = i;
		}
	}
	// 寻找到所有根节点中权值最小的weight1以后，继续寻找第二个
	// 找到数组中第一个根节点，作为初始权值最小的位置min2
	// 必须保证第min2不等于min1
	for (int i = 0; i < nums; i++) {
		if (p[i].parent == -1 && i != min1) {
			min2 = i;
			break;
		}
	}
	// 寻找数组中除去min1以外权值最小的根节点
	for (int i = 0; i < nums; i++) {
		if (p[i].parent == -1 && p[i].weight < p[min2].weight && i != min1) {
			min2 = i;
		}
	}
}

合并两棵树时，首先确保两棵树的根节点权重是所有根节点中最小的，然后将参与合并的两个根节点的权重相加以形成一个新的根节点（新树）. 最后，将新的根节点插入到数组中，并将合并的两个根节点的父节点设置为1（表示这两个根节点不再是根节点，而是树的子树哈夫曼树结点，并且以后将不再参与）在合并过程中）.

合并过程总共进行n-1次，并且用于创建霍夫曼树的相应总体代码如下:

void createHuffman(Node *p, int numLeafs) {
	// 1、初始化前numLeafs个根节点，指定其权值
	initLeafs(p, numLeafs);
	// 创建用于存储权值最小两个节点的位置
	int minPos1, minPos2;
	// 2、numLeafs个根节点需要进行numLeafs-1次合并
	for (int i = 0; i < numLeafs - 1; i++) {
		// 3、寻找权值最小的前两个节点
		// 寻找的范围是前numLeafs+i个节点
		// 即所有已经创建的节点
		searchMin(p, numLeafs + i, minPos1, minPos2);
		// 4、在numLeafs+1处创建新根节点
		p[numLeafs + i].weight = p[minPos1].weight + p[minPos2].weight;
		p[numLeafs + i].left = minPos1;
		p[numLeafs + i].right = minPos2;
		// 将当前权值最小的两个节点的parent指向新创建的根节点
		// 表示其不再是根节点，不再参与合并
		p[minPos1].parent = numLeafs + i;
		p[minPos2].parent = numLeafs + i;
	}
}

通过输出霍夫曼树的所有节点的所有信息，可以查看节点权重，左右子节点的位置，父节点的位置，然后确保代码正确:

void printHuffman(Node *p, int numNodes) {
	// 输出所有的节点，及节点信息
	for (int i = 0; i < numNodes; i++) {
		cout << setw(8) << p[i].weight <<
			setw(8) << p[i].parent <<
			setw(8) << p[i].left <<
			setw(8) << p[i].right << endl;
	}
}

【1】blog.csdn.net/One_castle/article/details/102980524

【2】yq.aliyun.com/articles/436501?spm=a2e.11155472.0.0.f9d54f0dhOvLy6

【3】cnblogs.com/wkfvawl/p/9783271.html

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-276385-1.html