chengxu.c

设置信号放大器

#include<iostream>
#define MAX 20
using namespace std;


struct node							//定义树的节点
{
	int key;						//节点编号
	int exisited;					//是否在该节点设置放大器
	int left,right;					//该节点的的子节点编号
	int lw,rw;					    //到该节点的衰减量
};

struct Tree							//定义树
{
	node a[MAX];					//数组存树的节点
	int n;							//节点个数
	int tolerance;					//容忍值
};

int D[MAX];							//节点i到以i为根节点的子树的叶子的衰减量的最大值
int d[MAX];							//节点i与其父节点之间的衰减量

void Start()						//初始化
{
	int i;
	for(i=0;i<MAX;i++)
		D[i]=d[i]=0;
}


void CreateTree(Tree &T)			//建立树型网络
{
	int i=0;
	cout<<"建立树，节点用编号表示，节点编号为1的点为根节点"<<endl<<"输入节点的总数目"<<endl;
	cin>>T.n;	
	T.a[i].key=T.a[i].left=T.a[i].right=T.a[i].lw=T.a[i].rw=T.a[i].exisited=0;
	
	for(i=1;i<=T.n;i++)
	{
		cout<<"输入第"<<i<<"个节点的左儿子编号，右儿子编号，左衰减量，右衰减量(叶子输入0 0 0 0)"<<endl;
		T.a[i].key=i;
		T.a[i].exisited=0;			//标记为0
		
		cin>>T.a[i].left>>T.a[i].right>>T.a[i].lw>>T.a[i].rw;
		
		d[T.a[i].left]=T.a[i].lw;	//节点T.a[i].left与其父节点i之间的衰减量
		d[T.a[i].right]=T.a[i].rw;	//节点T.a[i].right与其父节点i之间的衰减量
	}
	cout<<"输入容忍值的大小"<<endl;
	cin>>T.tolerance;
}




void SetAmplifier(Tree &T,int k)	//设置信号放大器
{
	int decr;						//衰减量		
	int y;
	y=T.a[k].left;					//考虑左儿子，y=0说明此时节点i的左儿子为空
	if(y)
	{
		decr=D[y]+d[y];
		if(decr>T.tolerance)		//说明左儿子要放置放大器			
		{
			T.a[y].exisited=1;
		}
		else D[k]=decr;				//否则把衰减量值赋给节点k
	}		
	y=T.a[k].right;
	if(y)							//考虑右儿子，y=0说明此时节点i的右儿子为空
	{
		decr=D[y]+d[y];
		if(decr>T.tolerance)
		{
			T.a[y].exisited=1;
		}
		else if(D[k]<decr)
			D[k]=decr;				//把衰减量的较大值赋给节点k
	}	
}



void PostOrder(Tree &T,int k)		//后续遍历，考虑每一棵子树
{	
	if(T.a[k].left==0&&T.a[k].right==0)				
		return;
	PostOrder(T,T.a[k].left);
	PostOrder(T,T.a[k].right);
	
	SetAmplifier(T,k);				//判断节点k的左右儿子是否要放置放大器
}



void PrintResult(Tree T)			//打印结果
{
	int i;
	for(i=1;i<=T.n;i++)
		if(T.a[i].exisited)
			cout<<"在第"<<i<<"个节点放置放大器"<<endl;
		
}
	

int main()
{
	char c;
	Tree T;
	
	do
	{
		Start();					//初始化
		CreateTree(T);				//建立树
		PostOrder(T,1);				//后序遍历
		
		PrintResult(T);		
		cout<<"是否继续(y/n)";
		cin>>c;
	}while(c=='y');
	return 1;
}