C/C++：哈夫曼树构建

哈夫曼树

参考地址：https://blog.csdn.net/yaoowei2012/article/details/18180769

#include <iostream>

using namespace std;

struct tree
{
	int data;
	struct tree *left;
	struct tree *right;
};

struct tree *createHaffman(int a[], int n)
{
	int i, j;
	struct tree **b, *q;
	b = (struct tree**)malloc(n*sizeof(struct tree));
	for (i = 0; i < n; i++)  //将数组构建成树的节点
	{
		b[i] = (struct tree*)malloc(sizeof(struct tree));
		b[i]->data = a[i];
		b[i]->left = NULL;
		b[i]->right = NULL;
	}
	for (i = 1; i < n; i++) // n-1循环建立哈夫曼树
	{
		int k1 = -1, k2;//k1表示森林中具有最小权值的树根节点的下标，k2为次最小的小标
		for (j = 0; j < n; j++)
		{
			if (b[j] != NULL && k1 == -1)
			{
				k1 = j;
				continue;
			}
			if (b[j] != NULL)
			{
				k2 = j;
				break;
			}
		}
		//cout << k1 << endl;//0
		//cout << k2 << endl;//1
		for (j = k2; j < n; j++)
		{
			if (b[j] != NULL)
			{
				if (b[j]->data < b[k1]->data)
				{
					k2 = k1;
					k1 = j;
				}
				else if (b[j]->data < b[k2]->data)
				{
					k2 = j;
				}
			}
		}
		//cout << k1 << endl;//3
		//cout << k2 << endl;//4
              //由最小权值树和次最小权值树建立一个新树，q指向树的根节点
		q = (struct tree*)malloc(sizeof(struct tree));
		q->data = b[k1]->data + b[k2]->data;
		q->left = b[k1];
		q->right = b[k2];
		
		b[k1] = q; //将指向新树的指针赋值给k1位置
		b[k2] = NULL;
	}
	free(b);
	return q;
}

int main()
{
	int data[6] = {9,12,6,3,5,15};
	cout << createHaffman(data, 6)->data << endl;
	system("PAUSE");
	return 0;
}

本文由 Ryan 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2019/09/02 18:36