2057目录树.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
#include<string.h>
struct node
{
	int left,right;
	char data[10];
};
node T[100000];
int head,tot;
char buf[1000];
void ins(int t,char *s)
{
	int p=t;
	int i;
	for(i=0;s[i]!='\\' && s[i]!='\0';i++)buf[i]=s[i];
	buf[i]='\0';
	while(1 )
	{
		if(strcmp(T[p].data,buf)==0)break;
		if(T[p].right==0)break;
		if(strcmp(T[p].data,buf)< 0 && strcmp(T[T[p].right].data,buf)>0)break;
		p=T[p].right;
	}
	if(strcmp(T[p].data,buf)==0)
	{
		char *ss=s+i;
		if(ss[0]=='\0')return ;
		ins(T[p].left,ss+1);
	}
	else
	{
		tot++;	
		int cur=tot;
		T[tot].left=0;T[tot].right=T[p].right;strcpy(T[tot].data,buf);
		T[p].right=tot;
		///
		tot++;
		T[tot].left=0;T[tot].right=0;strcpy(T[tot].data,"");
		T[cur].left=tot;
		///
		char *ss=s+i;
		if(ss[0]=='\0')return ;
		ins(tot,ss+1);
	}
	
}



void preorder(int t,int dep)
{
	int p=t;
	p=T[t].right;
	while(p)
	{
		int i;
		for(i=0;i<dep;i++)printf(" ");
		printf("%s\n",T[p].data);
		preorder(T[p].left,dep+1);
		p=T[p].right;
	}
}







int main()
{
	int i,j,k;
	
	int W,w;
	scanf("%d",&W);
	int n;
	char s[10000];
	for(w=1;w<=W;w++)
	{
		scanf("%d",&n);
		tot=1;
		T[tot].left=0;T[tot].right=0;strcpy(T[tot].data,"");
		for(i=1;i<=n;i++)
		{
			scanf("%s",s);
			ins(1,s);
		}
		if(w!=1)printf("\n");
		preorder(1,0);
	}
	return 0;


}