main.cpp

一个生成树的源程序

#include <iostream.h>


bool is_tree(char *start, int length)
{
	//in n array "0" represents this bit doesn't has a parent node or don't know yet
	//while "1" represents it does

	//initialize n array

	int i=0,j,n[100];			
	for(i=0;i<100;i=i+2) 
	{
		n[i]=0;				
		n[i+1]=1;				
	}
	
	//to see if there is the node which has more than one parent

	for(i=1;i<length;i=i+2)
		for(j=i+2;j<length;j=j+2)
			if(*(start+i)==*(start+j)) return false;

	//find all the nodes that has a parent node

	for(i=0;i<length;i=i+2)
		for(j=0;j<length;j++)
			if(n[j]&&j!=i&&*(start+i)==*(start+j)) {n[i]=1;j=length;}

	//to see if there's only one root

	for(i=0;i<length;i=i+2)
		if(!n[i]) {j=i;i=length;}
	for(i=j+2;i<length;i=i+2)				//j is the position of first bit that is supposed to be root
		if(!n[i]&&*(start+i)!=*(start+j))	//if two different roots are found
			return false;
	return true;
}

int get_length(char *start)
{
	int i=0;
	while(*(start+i)!='0'&&*(start+i)!='-')
		i++;
	return i;
}

void main()
{
	char seq[100];
	char *pointer=seq;
	int i=0,k=1;

	cout<<"Please enter the sequence:"<<endl;
	cin>>seq;

	do
	{
		i=get_length(pointer);
		if(is_tree(pointer,i)) cout<<"Case "<<k++<<" is a tree."<<endl;
		else cout<<"Case "<<k++<<" is not a tree."<<endl;
		pointer=pointer+i+2;

	}while(*(pointer)!='-');
}