main.cpp

本程序是实现二叉树跟树的常用算法

#include "binarytree.h"
#include "tree.h"

void main()
{
	BinaryTree<int> b;

	BinaryTree<char>b1;

	Tree<char> t;

	int change;
     
	while(1)
	{
	   cout<<"请选择:"<<endl<<endl;
		 
	   cout<<"(1)建立二叉树:"<<endl<<endl;

	   cout<<"(2)建立二树:"<<endl<<endl;

	   cout<<"(3)帮助:"<<endl<<endl;

	   cout<<"(4)退出:"<<endl<<endl;

	   cin>>change;

		 if(change == 4)

			 break;

	  switch(change)
	  {
	  case 1:

	    while(1)
	    {
		cout<<endl;

	    cout<<"选择建立二叉树的方法:"<<endl<<endl;
	
	    cout<<"(1)用嵌套括号表示法建立二叉树:"<<endl<<endl;

	    cout<<"(2)建立满二叉树:"<<endl<<endl;

	    cout<<"(3)建立排序二叉树:"<<endl<<endl;

	    cout<<"(4)用中序周游跟前序周游建立二叉树:"<<endl<<endl;
	
	    cout<<"(5)帮助:"<<endl<<endl;
	
	    cout<<"(6)退出:"<<endl<<endl;

	    cin>>change;

	    cout<<endl;

	    if(change==6)

		break;

	    char str[255];
	
	    int c=0,depth,i,j=0,k=0,sum=0,z=0,end[255],flag;

	 switch(change)
	 {

	 case 1:

		 cout<<"输入字符以等号结束:"<<endl;

		 for(i=0;i<255;i++)
		 {	
			 cin>>str[i];	
		
			 if(str[i]=='=')
			
				 break;	
		 }  
    
		 str[i]='\0';
	
		 flag=1;
	
		 b1.creatpackettree(str);		 	
	
		 break;

	 case 2:
	  
		 cout<<"输入数字以等号结束:"<<endl;

		 for(i=0;i<255;i++)	
		 {
		
			 cin>>str[i];		
		
			 if(str[i]=='=')
			
				 break;	
		 }
    
		 str[i]='\0';
	
		 i=0;
	
		 while(str[k]!='\0')	
		 {		
			 if(str[j]==','||str[j]=='\0')
			 {
				 for(k=i;k<j;k++)
				
					 sum=sum*10+str[k]-'0';			
			
				 end[z++]=sum;
			
				 sum=0;
			
				 i=j+1;
		
			 }
	   
			 if(str[j]!='\0')
		   
				 j++;	
		 }
    
		 end[z]='\0';
	
		 flag=2;
	
		 b.m_creatbrinarytree(end,z);
	
		 break;
	 
	 case 3:

		 cout<<"输入数字以等号结束:"<<endl;

		 for(i=0;i<255;i++)
		 {		
			 cin>>str[i];
		
			 if(str[i]=='=')
			
				 break;
		 }
    
		 str[i]='\0';
	
		 i=0;

	
		 while(str[k]!='\0')
		 {	
			 if(str[j]==','||str[j]=='\0')
			 {		
				 
				 for(k=i;k<j;k++)
				
					 sum=sum*10+str[k]-'0';			
			
				 end[z++]=sum;
			
				 sum=0;
			
				 i=j+1;
		}
	   
			 if(str[j]!='\0')
		   
				 j++;
		 }
    
		 end[z]='\0';
	
		 flag=3;
	
		 for(j=0;j<z;j++)	
	
			 b.CreatTree(end[j]);	
	
		 break;

	 case 4:

		 char pre[255],in[255];

		 int i;

		 cout<<"输入前序周游:"<<endl<<endl;

		 cout<<"输入字符以等号结束:"<<endl<<endl;

		 for(i=0;i<255;i++)
		 {	
			 cin>>pre[i];
				
			 if(pre[i]=='=')
			
				 break;
	   
		 }
         pre[i]='\0';
		 
		 cout<<"输入中序周游:"<<endl<<endl;

		 cout<<"输入字符以等号结束:"<<endl<<endl;

		 for(i=0;i<255;i++) 
		 {
		
			 cin>>in[i];
		
			 if(in[i]=='=')
			
				 break;
	   
		 }
    
		 in[i]='\0';

		 
		 flag=1;
		 
		 b1.pre_and_in_creatbinary(pre,in,strlen(pre));

		 break;

	 case 5:
          
		 cout<<"帮助:"<<endl<<endl;

		 cout<<"当你选择用嵌套括号表示法建立二叉树时,只能输入英文字符."<<endl<<endl;
		 
		 cout<<"输入格式:例如 a(b,c)="<<endl<<endl;

		 cout<<"当你选择排序二叉树或者满二叉树时，只能输入数字字符."<<endl<<endl;
	     
		 cout<<"输入格式:例如 12,3,2,6,7,="<<endl<<endl;

		 cout<<"当你选择用中序周游跟前序周游建立二叉树时，只能输入英文字符."<<endl<<endl;

		 cout<<"输入格式:例如:前序:a,b,c,= 中序:b,a,c,= "<<endl<<endl;

		 cout<<"注意:注意只有选择建立排序二叉树才可以进行删除."<<endl<<endl;

		 continue;

		 break;
        } 
    while(1)
	{
	cout<<endl;
		
	cout<<"请选择:"<<endl<<endl;
		
	cout<<"(1)打印二叉树:"<<endl<<endl;

    cout<<"(2)凹凸表示法:"<<endl<<endl;
    
	cout<<"(3)嵌套扩号表示法:"<<endl<<endl;

	cout<<"(4)非递归前序周游:"<<endl<<endl;

    cout<<"(5)非递归中序周游:"<<endl<<endl;

	cout<<"(6)非递归后序周游:"<<endl<<endl;

    cout<<"(7)非递归层次周游:"<<endl<<endl;

	cout<<"(8)二叉树叶结点个数:"<<endl<<endl;

	cout<<"(9)用队列求二叉树深度"<<endl<<endl;

    cout<<"(10)用栈求二叉树深度:"<<endl<<endl;

	cout<<"(11)中序线索二叉树:"<<endl<<endl;

	cout<<"(12)排序二叉树删除指定结点:"<<endl<<endl;

	cout<<"(13)改进的二叉排序树删除结点:"<<endl<<endl;

	cout<<"(14)打印指定结点的全部祖先:"<<endl<<endl;
	
	cout<<"(15)打印指定两个结点的最近祖先和彼此之间的距离:"<<endl<<endl;

	cout<<"(16)改进的非递归前序遍历:"<<endl<<endl;
	
	cout<<"(17)退出"<<endl<<endl;
	
	cin>>change;

	 if(change==17)

	 break;

	switch(change)
	{
	case 1:

		if(flag==2||flag==3){

			cout<<"\n"<<"打印二叉树:"<<endl<<endl;
	    
			b.PrintVTree();
		}
	
		else if(flag==1){

			cout<<"\n"<<"打印二叉树:"<<endl<<endl;
	
			b1.PrintVTree();
		}
	
		cout<<endl<<endl;

		break;
	
	case 2:

		if(flag==2||flag==3){

			cout<<"\n"<<"凹凸表示法:"<<endl<<endl;
	
			b.PrinTree();
		}
       
		else if(flag==1){

			cout<<"\n"<<"凹凸表示法:"<<endl<<endl;

			b1.PrinTree();
		}
	
		cout<<endl<<endl;
	
	    break;

	case 3:

		if(flag==2||flag==3){

			cout<<"\n"<<"嵌套扩号表示法:"<<endl<<endl;

			b.PackOrder();
		}
        
		if(flag==1){

			cout<<"\n"<<"嵌套扩号表示法:"<<endl<<endl;

			b1.PackOrder();
		}
	
		cout<<endl<<endl;
	
	    break;

	case 4:

		if(flag==2||flag==3){

			cout<<"\n"<<"非递归前序周游:"<<endl<<endl;

			b.PreOrder();
		}
        
		if(flag==1){

			cout<<"\n"<<"非递归前序周游:"<<endl<<endl;
			
			b1.PreOrder();
		}
	
		cout<<endl<<endl;

		break;

	case 5:

		if(flag==2||flag==3){

			cout<<"\n"<<"非递归中序周游:"<<endl<<endl;

			b.InOrder();
		}
        
		if(flag==1){

			cout<<"\n"<<"非递归中序周游:"<<endl<<endl;

			b1.InOrder();
		}
	
		cout<<endl<<endl;

		break;

	case 6:

		if(flag==2||flag==3){

			cout<<"\n"<<"非递归后序周游:"<<endl<<endl;

			b.PostOrder();
		}
        
		if(flag==1){

			cout<<"\n"<<"非递归后序周游:"<<endl<<endl;

			b1.PostOrder();
		}
	
		cout<<endl<<endl;

		break;

	case 7:

		if(flag==2||flag==3){

			cout<<"\n"<<"非递归层次周游:"<<endl<<endl;

			b.COrder();
		}
        
		if(flag==1){
            
			cout<<"\n"<<"非递归层次周游:"<<endl<<endl;
 
			b1.COrder();
		}
	
		cout<<endl<<endl;
	
        break;

	case 8:

		if(flag==2||flag==3){

			cout<<"\n"<<"二叉树叶结点个数:"<<endl<<endl;

			b.Countleaf(c);

			cout<<c;
		}
        
		if(flag==1){
			
			cout<<"\n"<<"二叉树叶结点个数:"<<endl<<endl;

			b1.Countleaf(c);

			cout<<c;
		}
	
		cout<<endl<<endl;

		break;

	case 9:

		if(flag==2||flag==3){

			cout<<"\n"<<"用队列求二叉树深度"<<endl<<endl;

			depth=b.Depth_queue();
		}
        
		if(flag==1){

			cout<<"\n"<<"用队列求二叉树深度"<<endl<<endl;

			depth=b1.Depth_queue();
		}
	
		cout<<depth<<endl<<endl;

		break;
    
	case 10:

		if(flag==2||flag==3){

			cout<<"\n"<<"用栈求二叉树深度"<<endl<<endl;

			depth=b.Depth_stack();

		}
        
		if(flag==1){

			cout<<"\n"<<"用栈求二叉树深度"<<endl<<endl;

			depth=b1.Depth_stack();
		}
	
		cout<<depth<<endl<<endl;

		break;

	case 11:

		   if(flag==2||flag==3)
		   
			   b.InThread();

		   if(flag==1)

			   b1.InThread();

		   while(1)
		   {

		   cout<<"请选择:"<<endl<<endl;

		   cout<<"(1)中序线索周游二叉树:"<<endl<<endl;

		   cout<<"(2)在中序线索二叉树中找指定结点在前序下的后缀:"<<endl<<endl;

		   cout<<"(3)在中序线索二叉树中找指定结点在后序下的前驱:"<<endl<<endl;

		   cout<<"(4)后序周游中序线索二叉树:"<<endl<<endl;

		   cout<<"(5)在中序线索二叉树中插入结点:"<<endl<<endl;
		   
		   cout<<"(6)退出:"<<endl<<endl;
		   
		   cin>>change;

		   if(change==6)
		   {
			    if(flag==2||flag==3)

					 b.MakeEmpty();

				 if(flag==1)

					 b1.MakeEmpty();

				 exit(1);
		   }

		   switch(change)
		   {
		   case 1:
			     if(flag==2||flag==3)
				 {
                    cout<<"中序线索周游二叉树:"<<endl<<endl;

					b.In_thread_Order();

					cout<<endl<<endl;
				 }
			    
				  if(flag==1)
				 {
                    cout<<"中序线索周游二叉树:"<<endl<<endl;

					b1.In_thread_Order();

					cout<<endl<<endl;
				 }

				 break;  
		   
		   case 2:
			     if(flag==2||flag==3)		   
				 {
					 cout<<"在中序线索二叉树中找指定结点在前序下的后缀:"<<endl<<endl;
			   
					 int data;
			   
					 cout<<"输入指定的结点:"<<endl<<endl;
			   
					 cin>>data;
               
					 b.FindNextinInorderTree(data);
		   
				 }
		   
				 if(flag==1)
				 {
			   
					 cout<<"在中序线索二叉树中找指定结点在前序下的后缀:"<<endl<<endl;
			   
					 char data;
			   
					 cout<<"输入指定的结点:"<<endl<<endl;
			   
					 cin>>data;
               
					 b1.FindNextinInorderTree(data);
		   
				 }
		   
				 break;
		   case 3:
                if(flag==2||flag==3)		   
				 {
					 cout<<"在中序线索二叉树中找指定结点在后序下的前驱:"<<endl<<endl;
			   
					 int data;
			   
					 cout<<"输入指定的结点:"<<endl<<endl;
			   
					 cin>>data;
               
					 b.FindBeforeinInorderTree(data);
		   
				 }
		   
				 if(flag==1)
				 {
			   
					 cout<<"在中序线索二叉树中找指定结点在后序下的前驱:"<<endl<<endl;
			   
					 char data;
			   
					 cout<<"输入指定的结点:"<<endl<<endl;
			   
					 cin>>data;
               
					 b1.FindBeforeinInorderTree(data);
		   
				 }
		   
				 break;
		   case 4:

			    if(flag==2||flag==3)
				 {
                    cout<<"后序周游中序线索二叉树:"<<endl<<endl;

					b.Post_Thread_Order();

					cout<<endl<<endl;
				 }
			    
				  if(flag==1)
				 {
                    cout<<"后序周游中序线索二叉树:"<<endl<<endl;

					b1.Post_Thread_Order();

					cout<<endl<<endl;
				 }

				 break;  
		   case 5:

			   if(flag==2||flag==3)
			   {
				   cout<<"在中序线索二叉树中插入结点:"<<endl<<endl;

				   int find_data,insert_data;

				   cout<<"输入线索二叉树中任意一个存在结点的值:"<<endl;

				   cin>>find_data;

				   cout<<"输入新插入结点的值:"<<endl;

				   cin>>insert_data;

				   b.InsertNode_in_Inthread(find_data,insert_data);
			   }

			   if(flag==1)
			   {
                   cout<<"在中序线索二叉树中插入结点:"<<endl<<endl;

				   char find_data,insert_data;

				   cout<<"输入线索二叉树中任意一个存在结点的值:"<<endl;

				   cin>>find_data;

				   cout<<"输入新插入结点的值:"<<endl;

				   cin>>insert_data;

				   b1.InsertNode_in_Inthread(find_data,insert_data);
			   }

			   break;
		   
		   }

		   }
		  break;  
     
    case 12:
		   
		if(flag==3)
		   {
			   cout<<"输入指定结点:"<<endl;

			   int del_data;

			   cin>>del_data;

			   b.Del_BinaryTreeNode(del_data);

			   cout<<"显示删了结点的二叉树"<<endl;

			   b.PrintVTree();

			   cout<<endl;
		   }

		   if(flag==1||flag==2)
		   {
			   cout<<"不可以进行删除"<<endl;
		   }
         
		   break;
	
	case 13:
		   
		if(flag==3)
		   {
			   cout<<"输入指定结点:"<<endl;

			   int del_data;

			   cin>>del_data;

			   b.Del_BinaryTreeNode_EX(del_data);

			   cout<<"显示删了结点的二叉树"<<endl;

			   b.PrintVTree();

			   cout<<endl;
		   }

		   if(flag==1||flag==2)
		   {
			   cout<<"不可以进行删除"<<endl;
		   }
         
		   break;

	case 14:

		if(flag==2||flag==3) 
		{
			  cout<<"输入指定结点:"<<endl;

			  int ancestor_data;

			  cin>>ancestor_data;

			  b.Ancestor(ancestor_data);

		}

		if(flag==1)
		{
			  cout<<"输入指定结点:"<<endl;

			  char ancestor_data;

			  cin>>ancestor_data;

			  b1.Ancestor(ancestor_data);

		}
         
		   break;

	case 15:

		if(flag==2||flag==3) 
		{
			  cout<<"输入两个指定结点(要从左子树输如，否则不能正确找出):"<<endl;

			  int ancestor_data1,ancestor_data2;

			  cin>>ancestor_data1>>ancestor_data2;

			  b.Closed_Ancestor(ancestor_data1,ancestor_data2);

		}

		if(flag==1)
		{
			  cout<<"输入两个指定结点(要从左子树输如，否则不能正确找出):"<<endl;

			  char ancestor_data1,ancestor_data2;

			  cin>>ancestor_data1>>ancestor_data2;

			  b1.Closed_Ancestor(ancestor_data1,ancestor_data2);
		}
         
		   break;

	case 16:

		if(flag==2||flag==3)
		{
			cout<<"改进的非递归前序遍历:"<<endl;

	        b.PreOrder_Ex();

		}

		if(flag==1)
		{
			cout<<"改进的非递归前序遍历:"<<endl;

	        b1.PreOrder_Ex();

		}

		break;
		   
}
}
}
break;
case 2:
	t.InsertChild('A');
	for(int i=0;i<3;i++)
	{
		t.Root();
		t.InsertChild('B'+i);
	}
	for(i=0;i<2;i++)
	{
		t.Root();
		t.FirstChild();
		t.InsertChild('E'+i);
	}
	    t.DisplayTree();
		break;

case 3:
	cout<<endl;
	cout<<"说明:"<<endl;
	cout<<"由于本人水平问题，导致建立树(动态左孩子/右孩子)表示法不能动态输入,"<<endl<<endl;
	cout<<"只能在程序中调用Root(),FirstChild()等函数来移动指针。希望其他高手"<<endl<<endl;
    cout<<"可以帮我改进.二叉树可以动态的输入,大家可以放心的使用."<<endl<<endl;

	break;

}
}
}