tree1.cpp

顺序存储二叉树 程序有简单的二叉树的输入

// 这是使用应用程序向导生成的 VC++ 
// 应用程序项目的主项目文件。

#include "stdafx.h"

#using <mscorlib.dll>

using namespace System;



#include <iostream>
using namespace std;
#define True 1
#define False 0
#define Ok 1
#define Error 0
#define Overflow -2
#define Maxsize 100

typedef int TET;
typedef TET SqBT[Maxsize+1];

//使二叉树为空
void EmptyBT(SqBT bt)ni
{
	int i;
	for(i=1;i<=Maxsize;i++)
		bt[i]=0;
}


//插入一个元素的算法
void Insert(SqBT bt)
{
	int k;TET e;
A:
	cout<<"输入位置：";
	cin>>k;
	cout<<"输入元素：";
	cin>>e;
	cout<<endl;
	if(bt[k])                                               //判断k位置是否已经有元素
	{
		cout<<"你输入的位置"<<k<<"已经有元素，请重新输入！"<<endl;
		goto A;
	}
	else if(k<=Maxsize && bt[k/2])                    //k是否合法
		bt[k]=e;
	else 
	{
		cout<<"##ERROR  你输入的地址k<=Maxsize 或 bt[k/2]处没有子叶，请再次出入！！"<<endl;
	    goto A;
	}
}


**********************************************************************************
//建立二叉树
void CreateBT(SqBT bt)
{
	int n,i;
	cout<<"输入你要插入的个数："<<endl;
	cin>>n;
	bt[0]=1;
//	cout<<"输入数据："<<endl;
	for(i=1;i<=n;i++)
		Insert(bt);
}

**********************************************************************************
//前序遍历顺序二叉树算法
void PreBT(SqBT bt,int i)
{
   if(i>=Maxsize||!bt[i])
	   return;
   printf("%3d ",bt[i]);
   PreBT(bt,2*i);
   PreBT(bt,2*i+1);
}

**********************************************************************************
//中序打印二叉树的树形算法
void InBT(SqBT bt,int i,int k)
{ 
	int j;
    if(i>=Maxsize||!bt[i])
		return;
    InBT(bt,2*i+1,k+10);
    for(j=0;j<k;j++) 
		cout<<" ";

//		printf(" ");
    printf("%d\n",bt[i]);
    InBT(bt,2*i,k+10);
}
**********************************************************************************
//后序遍历顺序二叉树算法
void PostBT(SqBT bt,int i)
{
   if(i>=Maxsize||!bt[i])
	   return;
   PostBT(bt,2*i);
   PostBT(bt,2*i+1);
   printf("%3d ",bt[i]);
}

**********************************************************************************
//前序输出
void QianxuPrint(SqBT bt)
{
	int i;
	cout<<"输入你要从哪个节点开始输入起子叶："<<endl;
	cin>>i;
	PreBT(bt, i);
}


**********************************************************************************
//中序输出
void ZhongxuPrint(SqBT bt)
{
	int i,k=1;
	cout<<"输入你要从哪个节点开始输入起子叶："<<endl;
	cin>>i;
//	cout<<"输入k："<<endl;
//	cin>>k;
	InBT(bt,i,k);
}
***********************************************************************************                                                                     
//后续输出
void HouxuPrint(SqBT bt)
{
	int i;
	cout<<"输入你要从哪个节点开始输入起子叶："<<endl;
	cin>>i;
	PostBT(bt, i);
}

***********************************************************************************
void Change(SqBT bt)
{
	int k;TET e;
A:
	cout<<"输入改变的位置 和 元素："<<endl;
	cin>>k>>e;
	if(k<=Maxsize && bt[k/2])
		bt[k]=e;
	else 
	{
		cout<<"##ERROR  请再次输入。"<<endl;
	    goto A;
	}
}

**********************************************************************************
//个数
int Menber(SqBT bt)
{
	int m=0,i=1;
	while(bt[i]!=0)
	{
		m++;
		i++;
	}
	return m;
}
//输出二叉树的子叶个数
int  Menprint(SqBT bt)
{
	cout<<"二叉树的子叶个数是："<<Menber(bt)<<endl;
	return Ok;
}
***********************************************************************************
// 在完全二叉树的末尾插入元素
int Insertone(SqBT bt)                       //  与void Insert(SqBT bt)相似！！
{

	int k;TET e;
A:
	cout<<"请输入插入的位置k：";
	cin>>k;
	cout<<"请输入元素e：";
	cin>>e;
	cout<<endl;
	if(bt[k])                                               //判断k位置是否已经有元素
	{
		cout<<"你输入的位置"<<k<<"已经有元素，请重新输入！"<<endl;
		goto A;
	}
	else if(k<=Maxsize && bt[k/2])                    //k是否合法
	{
		bt[k]=e;
		return Ok;
	}
	else 
	{
		cout<<"##ERROR  你输入的地址k<=Maxsize 或 bt[k/2]处没有子叶，退出此操作！！"<<endl;
	    return Error;
	}
}
******************************************************************************
//判断形状和元素值完全相同
int EqualSq(SqBT bt, SqBT bt1)
{

	int n=0,m=0;
	n=Menber(bt);
	cout<<"*****二叉树A的元素个数为："<<n<<endl
		<<"*****输入二叉树的 "<<n<<"个元素："<<endl;
	bt1[0]=1;
	for(int j=1;j<=n;j++) 
		Insert(bt1);
	for(int i=1;i<Maxsize;i++)
	   if(bt[i]!=bt1[i]) 
	   {
		   m++;
		   cout<<"你输入的二叉树B与以前的二叉树不同！！"<<endl;
	   }
	if(m==0)
		cout<<"你输入的二叉树B与以前的二叉树相同！！！"<<endl;
	return Ok;
	
}
*****************************************************************************
//清空二叉树
int Clear(SqBT a,SqBT b)
{
	char c;
	int m,n;
	cout<<"清空二叉树a还是b："<<endl;
	cin>>c;
	if(c=='a')
	{
		m=Menber(a);
		if(m==0)
		{
			cout<<"##二叉树a已经是空，退出此操作！！"<<endl;
			return Error;
		}
		else 
		{
			EmptyBT(a);
			cout<<"**二叉树b已经成功清空！！"<<endl;
		}
	}
	if(c=='b')
	{
		n=Menber(b);
		if(n==0)
		{
			cout<<"##二叉树b已经是空，退出此操作！！"<<endl;
			return Error;
		}
		else 
		{
			EmptyBT(b);
			cout<<"**二叉树a已经成功清空！！"<<endl;
		}
	}
	return Ok;
}


*********************************************************************
//求元素e在二叉树中层次
int FindNode(SqBT bt,int i,int e)//  made by 杨杨
{
	static k;  int k1;                     
    k++;
    if(i<Maxsize && bt[i] )
	{
		if(e==bt[i]) k1=k;
	    else if(!(k1=FindNode(bt,2*i,e))) 
			k1=FindNode(bt,2*i+1,e);    
	}
    else k1=0;
    k--;
    return k1;
}
//求元素e在二叉树中层次
int Search(SqBT bt)//  made by 杨杨
{
	int i,e,h;
	cout<<"输入你要查找的元素e："<<endl;
	cin>>e;
	cout<<"输入你要从第几个子叶开始查找："<<endl;
	cin>>i;
	h=FindNode(bt,i,e);
	if(h==0)
	{
		cout<<"二叉树中没有元素"<<e<<endl;
		return Error;
	}
	else
	{
		cout<<"二叉树中有元素"<<e<<endl;
		cout<<"且其在二叉树中层次是"<<h<<endl;
		return Ok;
	}
}
*****************************************************************
//求二叉树的深度//  made by 杨杨
int DepthBT(SqBT bt,int i)
{
	int k1,k2;
    if(i>=Maxsize||!bt[i]) return 0;
    k1=DepthBT(bt,2*i);
    k2=DepthBT(bt,2*i+1);
    return(1+((k1>=k2) ? k1 : k2));
 }
//求二叉树的深度
void Dep(SqBT bt)
{
	int i;
	cout<<"计算其子二叉树的层次,输入你要从哪个子叶开始i："<<endl;
	cin>>i;
	cout<<"从第"<<i<<"子叶i="<<bt[i]<<"开始的子叶层次为："<<DepthBT(bt,i)<<endl;
}

****************************************************************************









void windows()   //  made by 杨杨
{

	printf("\n             --------------------------------------------- \n");
	printf("             =                                              =\n");
	printf("             =     简单二叉树操作(5、6为两个二叉树的操作)   =\n");            
	printf("             =                                              =\n");
	printf("             ------------------------------------------------\n");
	printf("             =                                              =\n");
	printf("             =     1.  输入子叶元素                         =\n");
	printf("             =                                              =\n");
	printf("             =     2.  在树末尾插入元素                     =\n");
	printf("             =                                              =\n");
	printf("             =     3.  改变子叶的元素                       =\n");
	printf("             =                                              =\n");
	printf("             =     4.  输出子叶个数                         =\n");
	printf("             =                                              =\n");
	printf("             =     5.  判断二叉树的形状和元素值是否完全相同 =\n");
	printf("             =                                              =\n");
	printf("             =     6.  清空二叉树                           =\n");
	printf("             =                                              =\n");
	printf("             =     7.  求元素e在二叉树中层次                =\n");
	printf("             =                                              =\n");
	printf("             =     8.  求二叉树的深度                       =\n");
	printf("             =                                              =\n");
	printf("             =     9.  前序输出二叉树                       =\n");
	printf("             =                                              =\n");
	printf("             =     10. 中序输出二叉树                       =\n");
	printf("             =                                              =\n");
	printf("             =     11. 后序输出二叉树                       =\n");
	printf("             =                                              =\n");
	printf("             =     0.  退出单链表操作                       =\n");
	printf("             =                                              =");
	printf(" \n             ---------------------------------------------\n");
}

int main()
{
	int A[Maxsize+1],B[Maxsize+1];
    int choice;
	while(1)       //  进行一个操作后又回到窗口，  是用户选择下一操作！//  made by 杨杨
	{
		//system("cls");
		//  made by 杨杨
		windows();
		printf("           欢迎简单链表操作系统!!请输入您的选择 (0-8): ");
		cin>>choice;
		getchar();
		switch(choice)
		{
			case 1 : system("cls");   CreateBT(A);              break;
			case 2 : system("cls");   Insertone(A);             break;
			case 3 : system("cls");   Change(A);                break;
			case 4 : system("cls");   Menprint(A) ;             break;
			case 5 : system("cls");   Clear(A,B);               break;
			case 6 : system("cls");   Search(A);                break;
			case 7 : system("cls");   Dep(A) ;                  break;
			case 8 : system("cls");   EqualSq(A,B);             break;
			case 9 : system("cls");   QianxuPrint(A);           break;
			case 10 : system("cls");  ZhongxuPrint(A);          break;
			case 11 : system("cls");  HouxuPrint(A);            break;
			case 0 :                                            break;
			default:system("cls");printf("输入不正确! 请再次输入!!\n");
		}
		if(choice==0)
			break;
	}
	return 0;
}