Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

二叉树

Posted by lizeliang at 2009-06-29 11:00:59 on Problem 1002
#include<cstdio>
#include<cstring>

struct node
{
	char s[10];
	int number;
	node * left,* right;
};

void insert(char * a,node * root)
{
	node * pos=root;
	node * fapos=NULL;
	while(1)
	{
		if(pos)
		{
			if(strcmp(a,pos->s)>0)
			{
				fapos=pos;
				pos=pos->right;
			}
			else if(strcmp(a,pos->s)<0)
			{
				fapos=pos;
				pos=pos->left;
			}
			else
			{
				pos->number++;
				break;
			}
		}
		else
		{
			if(strcmp(a,fapos->s)>0)
				pos=fapos->right=new node;
			else
				pos=fapos->left=new node;
			strcpy(pos->s,a);
			pos->number=1;
			pos->left=pos->right=NULL;
			break;
		}
	}
}
void travel(node * root,int & n)
{
	int i;
	if(root)
	{
		travel(root->left,n);
		if(root->number>1)
		{
            n++;
			for(i=0;i<3;i++)
				printf("%c",root->s[i]);
			printf("-");
			for(i=3;i<7;i++)
				printf("%c",root->s[i]);
			printf(" %d\n",root->number);
		}
		travel(root->right,n);
	}
}
int main()
{
	char s[50],standard[10];
	int n,i,j,temp,count=0;
	node * root=NULL;
	scanf("%d",&n);
	temp=n;
	while(n--)
	{
		scanf("%s",s);
		i=j=0;
		while(s[i]!='\0')
		{
			if(s[i]>='0'&&s[i]<='9')
			{
				standard[j]=s[i];
				j++;
			}
			else if(s[i]>='A'&&s[i]<='O')
			{
				standard[j]=(s[i]-'A')/3+'2';
				j++;
			}
			else if(s[i]>='P'&&s[i]<='S')
			{
				standard[j]='7';
				j++;
			}
			else if(s[i]>='T'&&s[i]<='Y')
			{
				standard[j]=(s[i]-'T')/3+'8';
				j++;
			}
			i++;
		}
		standard[j]='\0';
		if(temp-1==n)
		{
		    root=new node;
		    strcpy(root->s,standard);
		    root->number=1;
		    root->left=root->right=NULL;
        }
        else
	        insert(standard,root);
	}
	travel(root,count);
	if(count==0)
	   printf("No duplicates. \n");
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator