【无标题】哈夫曼树的构造、权值 C语言代码实现

一、数据结构
（1）树的数据结构

typedef struct
{
	int data;
	int left, rigth, parent;
	
}HTNode,*HTree;

（2）排序链表的数据结构

typedef struct SNode
{
	int data;//存放weight值
	int Tnum;//存放结点在树中的编码
	struct SNode *next;
}SNode,*SString;

二、构造哈夫曼树

//Select的参数k：T中有k个带权值的结点
int Select(HTree T, int k, int& the1, int &the2)
{
  //声明新链表，用于存储待处理结点的数据、排序
	SString blue;
	blue = (SNode*)malloc(sizeof(SNode));
	SNode* head = blue;
	

	for (int i = 1; i <= k; i++)
	{
		if (T[i].parent==0)
		{
			SString t =(SNode*)malloc(sizeof(SNode));
			
			t->data = T[i].data;
			t->Tnum = i;
			t->next = NULL;
			head->next = t;
			head = t;
		}
	}
	head = blue->next;
	printf("待排序表中各节点的weight值如下：n");
	PrintList(blue);
  
  //根据链表中的weigth排序得到升序链表
	SString temp1 = blue->next;
	SString temp2 = temp1;
	for (int i = 1;temp1; i++)
	{
		temp2 = temp1;
		for (int j=i+1;temp2->next ; j++)
		{
			if ((temp2->data) >= (temp2->next->data))
			{
				int td, tt;
				td = temp2->data;
				temp2->data = temp2->next->data;
				temp2->next->data = td;

				tt = temp2->Tnum;
				temp2->Tnum = temp2->next->Tnum;
				temp2->next->Tnum = tt;			
			}
			temp2 = temp2->next;
		}
		temp1 = temp1->next;
	}
	printf("排序后表中各节点的weight值如下：n");
	PrintList(blue);

	the1 = head->Tnum;
	the2 = head->next->Tnum;
	
//	the1 ;//较小权值结点的编号
//	the2;//较小权值结点的编号

	std::cout << "此次得出权值最小的两个节点的标号为：" << the1 << "  " << the2 << "n";
	//最后返回weigth最小的两个结点的编码。
	return the1, the2;

}

HTree CreateHuffman(int a[],int n)
{
	int num = 2*n - 1; //对于哈夫曼树，有n个叶子节点，则有n-1个父节点
	HTree T=new HTNode[num+1];//第一个结点空置
	
	for (int i = 1; i <= n ; i++)//将编码为1~n的结点作为叶子节点
	{
		T[i].data = a[i - 1];
		T[i].left =0;
		T[i].rigth= 0;
		T[i].parent= 0;
	}
	

	for (int i = n+1; i <2*n; i++)//将编码为n+1~2n-1的结点作为父节点//次for循环为显示HT终态所准备，非必要部分
	{
		T[i].data = 0;
		T[i].left = 0;
		T[i].rigth = 0;
		T[i].parent = 0;
	}
	ShowHTree(T, num);

	for (int i = n+1; i <=num; i++)//将编码为n+1~2*n-1的结点作为父节点
	{
		int the1=0, the2=0;
		Select(T,i-1,the1,the2 );//比较编号为1~i-1且parent为0的结点，找出data最小的两个，返回其编号
		
		T[the1].parent = i; 
		T[the2].parent = i;

        T[i].left = the1; T[i].rigth = the2;
		T[i].data = T[the1].data + T[the2].data;
		
		std::cout <<"第"< 
三、求权值
 
void HTreeWeight(HTree T,int n)
{
	//计算权值有两种方法：（1）所有（叶子结点的权值*叶子结点的个数）的和
	//                    （2）所有非叶子节点的权值的和
	//此处采用第二种
	//参数n：叶子结点的个数
	int weight=0;
	for (int i = n + 1; i <= 2 * n - 1; i++)
	{
		weight = T[i].data + weight;

	}
	std::cout << "此哈夫曼树的权值为:"< 
四、最终代码
 
//树的数据结构
typedef struct
{
	int data;
	int left, rigth, parent;
	
}HTNode,*HTree;


//Select函数中排序链表的数据结构
typedef struct SNode
{
	int data;
	int Tnum;
	struct SNode *next;
}SNode,*SString;


// 打印链表中全部的元素。
void PrintList(SString S)
{
	if (S == NULL) 
	{ printf("链表不存在。n"); return; } // 判断链表是否存在。

	SString pp = S->next;  // 从第1个结点开始。

	while (pp)
	{
		
		printf(" %d ", pp->data);  // 如果元素ee为结构体，这行代码要修改。
		pp = pp->next;
	}

	printf("n");

}

//Select的参数k：T中有k个带权值的结点，
int Select(HTree T, int k, int& the1, int &the2)
{
	SString blue;
	blue = (SNode*)malloc(sizeof(SNode));
	SNode* head = blue;
	

	for (int i = 1; i <= k; i++)
	{
		if (T[i].parent==0)
		{
			SString t =(SNode*)malloc(sizeof(SNode));
			
			t->data = T[i].data;
			t->Tnum = i;
			t->next = NULL;
			head->next = t;
			head = t;
		}
	}
	head = blue->next;
	printf("待排序表中各节点的weight值如下：n");
	PrintList(blue);

	SString temp1 = blue->next;
	SString temp2 = temp1;
	for (int i = 1;temp1; i++)
	{
		temp2 = temp1;
		for (int j=i+1;temp2->next ; j++)
		{
			if ((temp2->data) >= (temp2->next->data))
			{
				int td, tt;
				td = temp2->data;
				temp2->data = temp2->next->data;
				temp2->next->data = td;

				tt = temp2->Tnum;
				temp2->Tnum = temp2->next->Tnum;
				temp2->next->Tnum = tt;			
			}
			temp2 = temp2->next;
		}
		temp1 = temp1->next;
	}
	printf("排序后表中各节点的weight值如下：n");
	PrintList(blue);

	the1 = head->Tnum;
	the2 = head->next->Tnum;
	
//	the1 ;//较小权值结点的编号
//	the2;//较小权值结点的编号

	std::cout << "此次得出权值最小的两个节点的标号为：" << the1 << "  " << the2 << "n";
	return the1, the2;

}

void ShowHTree(HTree T,int num)
{
	
	std::cout << "该HT的终态如下:n";
	std::cout << "结点编码  weigth  parent  lchild  rchild:n";
	for (int i = 1; i<=num; i++)
	{
		std::cout << "      " << i << "      " << T[i].data << "      " << T[i].parent << "      " << T[i].left << "      " << T[i].rigth << "n";
	}
}



HTree CreateHuffman(int a[],int n)
{
	int num = 2*n - 1; //对于哈夫曼树，有n个叶子节点，则有n-1个父节点
	HTree T=new HTNode[num+1];
	for (int i = 1; i <= n ; i++)//将编码为1~n的结点作为叶子节点
	{
		T[i].data = a[i - 1];
		T[i].left =0;
		T[i].rigth= 0;
		T[i].parent= 0;
	}
	

	for (int i = n+1; i <2*n; i++)//将编码为n+1~2n-1的结点作为父节点//次for循环为显示HT终态所准备，非必要
	{
		T[i].data = 0;
		T[i].left = 0;
		T[i].rigth = 0;
		T[i].parent = 0;

	}
	ShowHTree(T, num);

	for (int i = n+1; i <=num; i++)//将编码为n+1~2*n-1的结点作为父节点
	{
		int the1=0, the2=0;
		Select(T,i-1,the1,the2 );//比较编号为1~i-1且parent为0的结点，找出data最小的两个，返回其编号
		
		T[the1].parent = i; 
		T[the2].parent = i;

        T[i].left = the1; T[i].rigth = the2;
		T[i].data = T[the1].data + T[the2].data;
		
		std::cout <<"第"<> n;
    std::cout << "请输入叶子结点的权值:n";
	for (int i = 0; i < n; i++)
	{
		std::cin >> a[i];
	}


    HTree T1= CreateHuffman(a, n);

	HTreeWeight(T1,n);
	
	
}