2418.cpp

acm pku 2418算法题实现 acm pku 2418算法题实现

//Pku 2418 Hardwood Species
//二叉查找树
//注意释放内存,否则超内存

#include<iostream>

using namespace std;

const int LEN=31;  //定义最大外文长度

class BitNode
{
public:
	char key[LEN];  //外文
	int time;  //出现次数
	BitNode* lchild;
	BitNode* rchild;

	BitNode()
	{
		/*this->lchild=NULL;
		this->rchild=NULL;
		this->time=1;*/
	}
};

BitNode* head=NULL;
int sum;

void Insert(char* key)  //向二叉树中插入结点
{
	BitNode *p1,*p2;  //p2指示当前结点,p1指示p2的父结点
	p1=NULL;p2=head;
	while(p2 != NULL)
	{
		if(strcmp(key,p2->key)==0)  
		{
			p2->time++;
			//delete p;  //释放内存
			return;
		}
		p1=p2;
		p2=strcmp(key,p2->key)<0 ? p2->lchild:p2->rchild;  
		//由题意关键字唯一,所以不考虑关键字相同的情况
	}  //先判断是否已存在关键字,节省内存

	BitNode* p=new BitNode();
	p->lchild=NULL;
	p->rchild=NULL;
	strcpy(p->key,key);
	p->time=1;  //定义新结点,会占用内存

	if(head == NULL)
	{
		head=p;
	}
	else
	{
		if(strcmp(p->key,p1->key)<0)
		{
			p1->lchild=p;
		}
		else
		{
			p1->rchild=p;	
		}
	}
}

void InOrder(BitNode* head)
{
	if(head == NULL)  return;

	InOrder(head->lchild);
	printf("%s %.4f\n",head->key,head->time*100.0/sum);
	InOrder(head->rchild);
}

void run()
{
	char key[LEN];
	sum=0;
	while(gets(key))
	{
		Insert(key);
		sum++;
	}  //输入数据

	InOrder(head);

	delete head;  //释放内存
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("D:\\资料\\ACM设计\\ACM\\Pku University\\2418_1\\2418.txt","rt",stdin);
#endif

	run();
	return 0;
}