本文共 1403 字，大约阅读时间需要 4 分钟。

菜鸟生成记(46)

重温数据结构—最优二叉树

构造原理终于弄懂了,代码也能写出来了,就是查找的效率不太高,有待改进

#include<iostream>#include<algorithm>#include<vector>using namespace std;const int N=1e2+10;struct st{   	char ch; 	int w;	int pre;	int r,l;	st()//构造函数：成员初始化 	{   		pre=-1;//初始化-1：默认-1为没有父亲 		r=l=-1;//初始化-1：默认-1为没有儿子 		w=0; 	}}s[N];int x1[N]={   2,4,5,7};//初始权值 vector<int> a(x1,x1+4);//赋值给容器a int n=4,f[N]={   0};void find1(int &s1,int &s2)//寻找a容器中未被访问过的最小的两个元素的下标 {   //&引用类型, 通过形参,改变实参的值 	int x=-1,y=-1,min1=N,min2=N;	for(int i=0;i<a.size();i++)	{   		if(f[i]==1)//访问过,跳过 		continue;		if(min1>a[i])		{   			min1=a[i];			x=i;		}	}	f[x]=1;//访问标记 	for(int i=0;i<a.size();i++)	{   		if(f[i]==1)//访问过,跳过 		continue;		if(min2>a[i])		{   			min2=a[i];			y=i;		}	}	f[y]=1;//访问标记 	a.push_back(min1+min2);//最小的两个权值之和进入容器a,等待接下来最小的两个权值的评选 	s1=x;//两个最小权值的下标回传给实参 	s2=y;	}void createT()//构建最优树 {   //最优树最终节点数=2*n-1(n：初始结点数) 	for(int i=0;i<n;i++)//最初的n个结点,先占据最前的n个结点 	{   		s[i].w=a[i];	}	for(int i=n;i<2*n-1;i++)	{   		int x,y;		find1(x,y);//两个最小的权值下标 		s[i].r=x,s[i].l=y;//认左右儿子 		s[x].pre=i,s[y].pre=i;//认父亲 		s[i].w=s[x].w+s[y].w;//权值和 	}}	int main(){   //初始权值:2,4,5,7 	createT();	printf("编号	权值	父亲编号  右儿子编号  左儿子编号\n");	for(int i=0;i<2*n-1;i++)//pre=-1,r=-1,l=-1代表没有父亲,没有右儿子,没有左儿子 	{   		printf("i:%-5d  w:%-5d  pre:%-5d  r:%-5d  l:%-5d\n",i,s[i].w,s[i].pre,s[i].r,s[i].l);	}	cout<<endl;	for(int i=0;i<a.size();i++)//权值动态容器 	cout<<a[i]<<" ";		return 0;}