#include?

using?namespace?std;

struct?node?????????????????//定義樹的元素
{
????struct?node?*lchild;
????struct?node?*rchild;
????char?data?;
????int?weight;
????int?D;????????????????//當前衰減量最大值
};
typedef?struct?node?*?BTREE?;

typedef?enum{L?R}?tagtype;

typedef?struct
{
????BTREE?ptr;
????tagtype?tag;
}stacknode;

typedef?struct
{
????stacknode?Elem[100];
????int?top;
}?Stack;

stacknode?Pop（?Stack?&S?）
{
????stacknode?c;
????c=S.Elem[?S.top?];
????S.top?=?S.top?-?1?;
????return?c;
}

void?Push?（?stacknode?x?Stack?&S?）
{
????S.top?=?S.top?+?1?;
????S.Elem[?S.top?]?=?x?;
}

typedef?struct
{
????char?data?parent?tag?;
????int?weight;
}?Bnode;

typedef?struct???????????//隊列
{
????BTREE?ele[100];
????int?frontrear;
}Squeue;

void?Makenull?（?Squeue?&Q）
{
????Q.front?=?0;
????Q.rear?=99;
}

BTREE?CreatBT（?）???????????????????//按邏輯結構建立二叉樹，依次輸入結點、父結點、標號、權值
{
????cout<<“請按邏輯結構輸入二叉樹“<????Bnode?p;
????Squeue?q;
????BTREE?root?s;
????root=new?node;
????root=NULL;
????Makenull（q）;
????cin>>p.data>>p.parent>>p.tag>>p.weight;
????while?（p.data!=‘0‘）
????{
????????s=new?node;
????????s->data=p.data;
????????s->weight=p.weight;
????????s->lchild=s->rchild=NULL;
????????q.rear=（q.rear+1）%100;
????????q.ele[q.rear]=s;
????????if?（p.parent==‘0‘）
????????????root=s;
????????else
????????{
????????????while?（q.rear+1%100!=q.front&&q.ele[q.front]->data!=p.parent）
????????????????q.front=（q.front+1）%100;
????????????if?（q.ele?[q.front]->data==p.parent）
????????????{
????????????????if?（p.tag==‘L‘）
????????????????????q.ele[q.front]->lchild=s;
????????????????else
????????????????????q.ele[q.front]->rchild=s;
????????????}
????????}
????????cin>>p.data>>p.parent>>p.tag>>p.weight;
????}
????return?root;
}

void?Amplifier（BTREE?sbint?tol）?????????????????????//設置信號放大器函數
{
????BTREE?t;
????Stack?s;
????stacknode?x;
????s.top=0;
????t=sb;
????do
????{
????????while?（t!=NULL）
????????{
????????????x.ptr?=?t;
????????????x.tag?=?L;
????????????Push（xs）;
????????????t=t->lchild;
????????}
????????while?（s.top!=0&&?s.Elem[s.top].tag==R）
????????{
????????????x?=?Pop（s）;
????????????t?=?x.ptr;
????????????if?（t->lchild==NULL&&t->rchild==NULL）
????????????{
????????????????t->D=0;??????????????????????????//初始化
????????????}
????????????else?if?（t->lchild==NULL&&t->rchild!=NULL）
????????????{
????????????????t->D=t->rchild->D+t->rchild->weight;??????????????//只有右子樹時當前最大衰減量
????????????????if?（t->D>tol）??????????????????//大于容忍值則設置放大器
????????????????{
????????????????????cout<<“應該放置放大器的結點為：“;
????????????????????cout<rchild->data<????????????????????t->D=t->rchild->weight;
????????????????}

????????????}
????????????else?if?（t->lchild!=NULL&&t->rchild==NULL）??????//只有左子樹時當前最大衰減量
????????????{
????????????????t->D=t->lchild->D+t->lchild->weight;
????????????????if?（t->D>tol）??????????????????//大于容忍值則放置放大器
????????