14_3_1.cpp

王红梅编《数据结构》大多数的实验源码。内附详细的实验报告。

#include <iostream.h>
#include "Queue.cpp"

struct Element
{
	int D;
	int d;
	bool boost;
};

struct BiNode
{
	Element data;
	BiNode *lchild, *rchild;
};

/*
@ CreateTree
前置条件：	二叉树不存在
输入：		根结点和扩展前序遍历序列
功能：		建立一棵新的二叉树
输出：		二叉树根节点的指针
后置条件：	二叉树被建立
*/
BiNode *CreateTree(BiNode *root)
{
	char ch;
	cin >> ch;
	if (ch == '#')
		return NULL;
	else
	{
		root			= new BiNode;
		root->data.d		= (int)ch - (int)'0';
		root->lchild		= CreateTree(root->lchild);
		root->rchild		= CreateTree(root->rchild);
		root->data.boost	= false;
		return root;
	}
}

/*
@ Max
前置条件：	存在两个数
输入：		两个数
功能：		取最大值
输出：		两个数中的最大值
后置条件：	数不变
*/
int Max(int a, int b)
{
	if (a > b)
		return a;
	else
		return b;
}

/*
@ D
前置条件：	二叉树存在
输入：		树的根结点和容忍值
功能：		取D(i)值
输出：		D(i)值
后置条件：	二叉树不变
*/
int D(BiNode *node, int tolerance)
{
	if (tolerance > 0 && node->data.boost)
		return tolerance - 1;
	if (node == NULL)
		return 0;
	if (node->lchild == NULL && node->rchild == NULL)
		return 0;
	else if (node->lchild != NULL && node->rchild == NULL)
	{
		return D(node->lchild, tolerance) + node->lchild->data.d;
	}
	else if (node->lchild == NULL && node->rchild != NULL)
	{
		return D(node->rchild, tolerance) + node->rchild->data.d;
	}
	else
	{
		return Max( D(node->lchild, tolerance) + node->lchild->data.d ,
					D(node->rchild, tolerance) + node->rchild->data.d );
	}
}

/*
@ SetD
前置条件：	二叉树存在
输入：		二叉树的根结点
功能：		后序遍历并设置D值
输出：		无
后置条件：	二叉树被设置了D值
*/
void SetD(BiNode *root)
{
	if (root == NULL)
		return;
	SetD(root->lchild);
	SetD(root->rchild);
	root->data.D = D(root, 0);
}

/*
@ PutBoost
前置条件：	二叉树存在
输入：		二叉树的根结点和容忍值
功能：		在合适的位置置入放大器
输出：		无
后置条件：	二叉树被置入了放大器
*/
void PutBoost(BiNode *root, int tolerance)
{
	if (root == NULL)
		return;
	PutBoost(root->lchild, tolerance);
	PutBoost(root->rchild, tolerance);
	
	if (root->lchild != NULL)
		if (root->lchild->data.D + root->lchild->data.d > tolerance)
			root->lchild->data.boost = true;
		else
			root->data.D = Max(root->data.D,
							   root->lchild->data.D + root->lchild->data.d);
	if (root->rchild != NULL)
		if (root->rchild->data.D + root->rchild->data.d > tolerance)
			root->rchild->data.boost = true;
		else
			root->data.D = Max(root->data.D,
							   root->lchild->data.D + root->lchild->data.d);
}

/*
@ PrintBoost
前置条件：	二叉树存在
输入：		二叉树的根结点
功能：		打印放大器
输出：		放大器所在的结点
后置条件：	二叉树不变
*/
void PrintBoost(BiNode *root)
{
	if (root == NULL)
		return;
	Queue<BiNode *> q;
	q.EnQueue(root);
	char i = 'A';
	while (!q.Empty())
	{
		BiNode *p = q.DeQueue();
		if (p->data.boost)
			cout << i << endl;
		if (p->lchild != NULL)
			q.EnQueue(p->lchild);
		if (p->rchild != NULL)
			q.EnQueue(p->rchild);
		i++;
	}
}

/*
@ DestroyTree
前置条件：	二叉树存在
输入：		二叉树的根结点
功能：		销毁二叉树
输出：		无
后置条件：	二叉树被销毁
*/
void DestroyTree(BiNode *root)
{
	if (root == NULL)
		return;
	DestroyTree(root->lchild);
	DestroyTree(root->rchild);
	delete root;
}

void main()
{
	BiNode *root;
	cout << "请输入树的扩展前序遍历，全为结点的d值：" << endl;
	// 书上的例子为：0122##1##2##312###22###
	root = CreateTree(root);
	SetD(root);
	int tolerance;
	cout << "请设置容忍值：" << endl;
	cin >> tolerance;
	PutBoost(root, tolerance);
	cout << "有放大器的结点为：" << endl;
	PrintBoost(root);
	DestroyTree(root);
}