2796770_re.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
#define INIT (node *)malloc(sizeof(node))

using namespace std;

struct node
{
	char name[21];
	node *l, *r;
	node *fa;
};

node *root;

void print(node *t,int n)
{
	int i;

	if(t==NULL)
		return ;
	for(i = 0; i < n; i++)
		printf("+");
	printf("%s\n",t->name);
	if(t->l)
		print(t->l,n+1);
	if(t->r)
		print(t->r,n);
}

node *bfs(char str[])
{
	node *t;
	queue <node *> que;

	if(strcmp(root->name,str)==0)
		return root;
	que.push(root);
	while(!que.empty())
	{
		t = que.front();
		que.pop();
		if(t->l)
		{
			if(strcmp(t->l->name,str)==0)
				return t->l;
			else
				que.push(t->l);
		}
		if(t->r)
		{
			if(strcmp(t->r->name,str)==0)
				return t->r;
			else
				que.push(t->r);
		}
	}
	return NULL;
}

void hire(char str[],char tmp[])
{
	node *t;

	t = bfs(str);
	if(t==NULL)
		return ;
	node *p;
	p = INIT;
	strcpy(p->name,tmp);
	p->l = p->r = NULL;
	if(t->l)
	{
		t = t->l;
		while(t->r)
			t = t->r;
		t->r = p;
		p->fa = t;
	}
	else
		t->l = p,p->fa = t;
}

void fire(char str[],node *q,char ch)
{
	node *t, *fa;

	t = bfs(str);
	if(t==NULL)
		return ;
	fa = t->fa;
	if(t->l==NULL&&t->r==NULL)
	{
		if(fa==NULL)
			root = NULL;
		else
		{
			if(fa->l==t)
				fa->l = NULL;
			else
				fa->r = NULL;
		}
		return ;
	}
	while(t->l)
	{
		strcpy(t->name,t->l->name);
		t = t->l;
	}
	t->r->fa = t->fa;
	t->fa->l = t->r;
}

int main()
{
	char tmp[21], str[21];

	root = INIT;
	scanf("%s",root->name);
	root->l = root->r = NULL;
	root->fa = NULL;
	while(scanf("%s",tmp)==1)
	{
		if(strcmp(tmp,"print")==0)
		{
			print(root,0);
			puts("------------------------------------------------------------");
		}
		else
			if(strcmp(tmp,"fire")==0)
			{
				scanf("%s",tmp);
				fire(tmp,root,'Y');
			}
			else
			{
				scanf("%s",str);
				scanf("%s",str);
				hire(tmp,str);
			}
	}
	return 0;
}