bstree1.cpp

简单二叉树的连表算法

// BSTree1.cpp : Defines the entry point for the console application.
//

//University community class and derived classes
//File univ.h
#include<stdio.h>
#include<string.h>
#include<iostream.h>
#include<fstream.h>
class univ_community 
{
	friend class tree;
protected:
	char last_name[15];
	char first_name[15];
	int age;
	long social_security_number;
public:
	univ_community(char *ln,char *fn,int a,long ss)
	{
		strcpy(last_name,ln);
		strcpy(first_name,fn);
 		age=a;
 		social_security_number=ss;
	}
	univ_community(){last_name[0]='\0';
	first_name[0]='0';
 	age=0;
 	social_security_number=0;
	}
	void set_last_name(char *last_n)
	{
		strcpy(last_name,last_n);
	}
	void set_first_name(char *first_n)
	{
		strcpy(first_name,first_n);
	}
 	void set_age(int a)
	{
		age=a;
	}
	void set_social_security_number(long soc_sec)
	{
		social_security_number=soc_sec;
	} 
	virtual void print()
	{
		cout<<endl<<last_name
			<<first_name<<"Age:"<<age<<endl
			<<"Social Security #"<<social_security_number;
		 
	}
};
class student:public univ_community
{
	friend class tree;
private:
	float grade_point_average;
	int level;
public:
	student(char *ln,char *fn,int a,long ss,float av,int i):(ln,fn,a,ss)  
	{
	 	grade_point_average=av;
	 	level=i;
	}
	student():() 
	{
		grade_point_average=0.0;
		level=0;
	}
	void set_average(float av)
	{
		grade_point_average=av;
	}
	void set_level(int l)
	{
		level=l;
	}
	void print()
	{
		univ_community::print();
		cout<<endl<<"grade point average:"<<grade_point_average
			<<endl<<"level:"<<level;
	}
}; 
class professor:public univ_community
{
	friend class tree;
private:
	float annual_salary;
public:
	professor(char *ln,char *fn,int a,long ss,float s):(ln,fn,a,ss)
	{
		annual_salary=s;
	}
	professor():()
	{
		annual_salary=0.0;
	}
	void set_annual_salary(float as)
	{
		annual_salary=as;
	}
	void print()
	{
		univ_community::print();
		cout<<endl<<"Annual Salary:"<<annual_salary;
	}
};
class staff:public univ_community
{
	friend class tree;
private:
	float hourly_salary;
public:
	staff(char *ln,char *fn,int a,long ss,float s):(ln,fn,a,ss)
	{
		jourly_salary=s;
	}
	void set_hourly_salary(float hs)
	{
		hourly_salary=hs;
	}
	void print()
	{
		univ_community::print();
		cout<<endl<<"Hourly Salary:"<<hourly_salary
	}
};
class dean:public univ_community
{
	friend class tree;
private:
	int years_in_service;
	int college;
public:
	dean(char *ln,char *fn,int a,long ss,int yr,int c):(ln,fn,a,ss)
	{
		years_in_service=yr;
		college=c;
	}
	dean():()
	{
		years_in_service=0;
		college=c;
	}
	void set_years(int yr)
	{
		years_in_service=yr;
	}
	void set_college(int c)
	{
		college=0;
	}
	void print()
	{
		univ_community::print();
		cout<<endl<<"College:"<<college
			<<endl<<"Years in Serice"<<years_in_serice;
	}
};
//Search tree constructon
class node{
	friend class tree;
private:
	node *left,*right;
	univ_community *data;
};
class tree
{
private:
	node *root;
	node *left;
	node *right;
public:
	tree()
	{
		root=left=right=NULL;
	}
	void insert_person(univ_community *a);
	void display(node *n=NULL,int first=1);
};
void tree::display(node *n,int first)
{
	node *current;
	if(first)
	{
		current=root;
		first=0;
	}
	else current=n;
	if(current!=n)
	{
		display(current->left,first);
		current->data->print();
		display(current->right,first);
	}
}
void tree::insert_person(univ_community *a)
{
	node *parent,*current;
	int found=0;
	parent=0;
	current=root;
	while(current && !found)
	{
		if(strcpy(current->data->last_name,a->last_name)==0)
			found=1;
		else
		{
			parent=current;
		}
		if(strcmp(a->last_name,current->data->last_name)<0)
			current=current->left;
		else current=current->right;
	}
	if(!found)
	{
		if(!parent)
		{
			//First node in tree
			root=new node;
			root->left=root->right=NULL;
			root->data=new univ_community;
			root->data=a;
		}
		else
		{
			if(strcmp(a->last_name,parent->data->last_name)<0)
			{
				//Add new node to the left of parent
				node *new_node=new node;
				new_node->data=a;
				new_node->left=new_node->right=0;
				parent->left=new_node;
			}
			else
			{//Add new node to the right of parent 
				node *new_node=new node;
				new_node->data=a;
				new_node->left=new_node->right=NULL;
				parent->right=new_node;
			}
		}
	}
}
int main(int argc,char* argv[])
/*Pre:Name of input and output files are given as command-line arguments.
  Post:Reads an input file that contain lines(character strings),performs simple
  editing operations on the lines,and wries the edited version to the output files.
  Uses: */  
{
	int i=0,j=0;
	int   array[length]  ;
//	CircList list; 
    tree tr;
   	ifstream file_in;     //Declare and open the input file.  
 	file_in.open("F:\\file_in.txt",ios::in);
	//the input file is in the F disk.
  	if(!file_in.is_open())   
		//If the file_in doesn't exist,the function will tell the 
	    //users that opening file fail.
	{
		cout<<"*************Open file fail!*****************"<<endl;
	}
 	else   //Or tell the users that the aim of this function. 
	{
		cout<<"This lab is designed to give us an experience of" 
			<<"writting C++ linked list class and its client program."
			<<"In this lab, there are designing implement and text a "
			<<"circular linked queue class which has functions and " 
			<<"data members  as other linked queue classes in the" 
			<<"textbook."<<endl 
			<<"This lab is based on C++. "<<endl;
		cout<<endl;
		cout<<endl;
		cout<<"Before change the sequences:" <<endl;
		for(i=0;i<10;i++)
		{
		 	file_in>>array[i];  //Read numbers from file_in.
			cout<<array[i]<<' '<<flush;
		}

 	for(j=0;j<length;j++)  //Arrante the sequence of the data.
		{
			for(i=j+1;i<length;i++)
			{
				if(array[i]>array[j])
				{
					int temp=array[i];
					array[i]=array[j];
					array[j]=temp;
				}
 				
			}
		}
	} 
	
   	ofstream file_out;   //   Declare and open the output file.
	file_out.open("F:\\file_out.txt");//, ios::out);
	//    the output file is in the F disk.  
 	if(!file_out.is_open())
	{
		cout<<"****************Open file fail!****************"<<endl;
   	}
 	else
	{
		cout<<endl;
		cout<<"After change the sequence of the data:" <<' '<<endl;
		file_out<<"After change the sequence of the data:"<<endl;
		for(i=0;i<length;i++)
		{
 			file_out <<array[i]<<' '<<flush;

			cout<<array[i]<<' '<<flush;
		}
  
		cout<<endl;
//Close file_in and file_out to protect the data of the two files.	
	file_in.close();  
  	file_out.close();
	}
	return 0;
}