设置信号放大器 一、树的存储结构 struct node 定义树的节点 { int.doc

设置信号放大器 一、树的存储结构: 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与其父节点之间的衰减量 二、算法思想 将实际问题转化成树形网络，用二叉树模拟。树边的权值为衰减量。 采用后序遍历，针对树的每一个节点判断其左右子节点是否放置放大器，并给该节点以其为根节点的子树的叶子的衰减量的最大值数组赋值。 三、运行结果 输入如下图所示的树：（容忍值输入3） 1 3 2 2 1 2 2 2 1 2 程序截图： 三、代码 #includeiostream #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;iMAX;i++) D[i]=d[i]=0; } void CreateTree(Tree T) //建立树型网络 { int i=0; cout建立树，节点用编号表示，节点编号为的点为根节点endl输入节点的总数目endl; cinT.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)endl; T.a[i].key=i; T.a[i].exisited=0; //标记为 cinT.a[i].leftT.a[i].rightT.a[i].lwT.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; cinT.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(decrT.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(decrT.tolerance) { T.a[y].exisited=1; } else if(D[k]decr) D[k]=decr; //把衰减量的