set_signal.cpp

数据结构中的经典问题

#include<iostream>

#define MAXNUM 128

using namespace std;

int tolerance;      //容忍值——全局变量

//二元树的“型”
struct node
{
	struct node *lchild;
	struct node *rchild;
	char vertex;
	int D;         //该结点到其父结点的衰减量
	int d;         //该结点到叶结点的衰减量
	bool boost;    //标记是否设置信号放大器
};
typedef struct node * BTREE;
BTREE T;

//创建一个带权值的二元树
void CreateBtree(BTREE &T)
{
	char ch;
	int count;
	
	cin >> ch;
	if(ch != '#')
		cin >> count;
	if(ch == '#')
		T = NULL;
	else
	{
		T = new node;
		T -> vertex = ch;
		T -> d = count;
		CreateBtree(T -> lchild);
		CreateBtree(T -> rchild);
	}
}

//判断是否该在x处设置信号放大器
void PlaceBoosters(node * x)
{
	BTREE y = x -> lchild;
	int degradation;
	x -> D = 0;
	if(y)
	{
		degradation = y -> D + y -> d;
		if(degradation > tolerance)
		{
			y -> boost = true;
			return ;
		}
		else
			x -> D = degradation;
		y = y -> lchild;
	}
	y = x -> rchild;
	if(y)
	{
		degradation = y -> D + y -> d;
		if(degradation > tolerance)
			y -> boost = true;
		else if(x -> D < degradation)
			x -> D = degradation;
		y = y -> rchild;
	}
}

//后序遍历设置放大器
void Postorder(BTREE &T)
{
	struct node *p = T;
	if(p != NULL)
	{
		Postorder(p -> lchild);
		Postorder(p -> rchild);
		p -> boost = false;
		PlaceBoosters(p);
	}
}

//后序遍历二元树并输出结果
void Show(BTREE &T)
{
	struct node *p = T;
	if(p != NULL)
	{
		Show(p -> lchild);
		Show(p -> rchild);
		if(p -> boost == true)
		{
			cout << p -> vertex;
		}
	}
}

int main()
{
	/*二元树输入规则：先序输入，以'#'表示空，先输入
	顶点然后是该顶点到其父节点的衰减量，其间要加空格*/
	cout << "请输入二元树：";
	CreateBtree(T);
	
	cout << "请输入容忍值：";
	cin >> tolerance;
	Postorder(T);
	
	cout << "应在以下结点处设置放大器： ";
	Show(T);
	
	return 0;
}