tree2.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 Status;
typedef char TET;
typedef TET SqBT[Maxsize+1];

typedef struct Btn{
       TET data;
       struct Btn *lchild , *rchild;
    }BTN ,*BT;



//建立二叉树
//Status CreateBT(BT &T)
//{
//	char ch;
//	cin>>ch;
//	if(ch==' ')  T=NULL;
//	else if(ch=='#')
//		return Ok;
//
//	else 
//	{
//		if(!(T=(BTN *)malloc(sizeof(BTN))))  
//			exit(Overflow);
//		T->data=ch;
//		CreateBT(T->lchild);
//		CreateBT(T->rchild);
//	}
//	return Ok;
//}
//建立二叉树*************************************************************
void CreateBT( BT  &T)   //, int k, int m)//  made by 杨杨
{ 
     BT  nar[50],p,q;// 用于存储各结点的地址
	 int j,k,m,n=1,parent;
	 char x;
     cout<<"输入你要建立二叉树的层数：";
	 cin>>k;
//     n=Cpow(2,k)-1;
	 for(int a=1;a<=k;a++)
		 n*=2;
	 n=n-1;
	 cout<<endl<<"你建立的"<<k<<"层二叉树最多要"<<n<<"个元素。"<<endl;
	 cout<<"请输入你要输入的元素个数："<<endl;
	 cin>>m;
	 for(int i=1;i<=n;i++)
		 nar[i]=NULL;
     for(i=1;i<=m;i++)
	 {
		 cout<<"输入结点的编号 j 和 数据域值 x:";
		 cin>>j>>x;
		 p=(BT )malloc(sizeof(BTN));  nar[j]=p ;
         p->data=x ; p->lchild=NULL; p->rchild=NULL; 
         if(j==1)  T=p ;
         else
	    { 
		    parent=(int)(j/2);  
		    q=nar[parent];
            if( j% 2) q-> rchild=p;
            else   q->lchild=p; 
		}
	 } 
}//


//前序输出*******************************************************//  made by 杨杨
void PreOrderT(BT  T)
{
   if(T){
	   cout<<" "<<T->data;
      PreOrderT(T->lchild);
      PreOrderT(T->rchild);
   }
}


//中序遍历*********************************************************//  made by 杨杨
void InOrderT(BT   T)
{
    if(T)
	{
        InOrderT(T->lchild);
         cout<<" "<<T->data;
        InOrderT(T->rchild);
    }
}


//后序遍历***********************************************************
void PostOrderT(BT   T)//  made by 杨杨
{
 if(T){
     PostOrderT(T->lchild);
     PostOrderT(T->rchild);
      cout<<" "<<T->data;
    }
}

//计算结点个数********************************************************//  made by 杨杨
int Number(BT T)
{
	int x=0,y=0;
	if(T==NULL)
	{
		return Error;
	}
	x=Number(T->lchild);
	y=Number(T->rchild);
	return (x+y+1);
}
void Num(BT T)
{
	cout<<"子叶个数是："<<Number(T)<<endl;
}


//求二叉树的高度*****************************************************
int High(BT T)
{
	int a,b;
	if(T==NULL)  return Error;
	a=High(T->lchild);
	b=High(T->rchild);
	return 1+((a>b)?a:b);
}
void HIGH(BT T)
{
	cout<<"二叉树的高度是："<<High(T)<<endl;
}

//查找元素的位置******************************************************
BT GetE(BT T,int e)
{
	BT p;
	if(T==NULL)  return Error;
	if(T->data==e)    return T;

	if(!int(p=GetE(T->lchild,e)))
		p=GetE(T->rchild,e);
	return p;
}
void Serach(BT T)
{
	int e;
	BT t;
	cout<<"输入你要查找的元素："<<endl;
	cin>>e;
	t=GetE(T,e);
	if(t->lchild==NULL)
		cout<<"元素"<<e<<"的左节点为空！"<<endl;
	else
		cout<<"元素"<<e<<"的左节点为:"<<t->lchild->data<<endl;
	if(t->rchild==NULL)
		cout<<"元素"<<e<<"的右节点为空！"<<endl;
	else
		cout<<"元素"<<e<<"的右节点为:"<<t->rchild->data<<endl;
}


//用前序递归统计每层的结点数*************************************************
void  ProLeveNum(BT T ,int A[ ])
{

// 数组A的初值为全0，A[0]记录树的高度，其余元素记录每层的结点数
    static  k;   // k为递归层次，也就是结点T在树中的层次
    k++;
    if(T)
	{  
		A[k]++;
        if(k>A[0])    A[0]=k;
        ProLeveNum(T->lchild, A);
        ProLeveNum(T->rchild,A);
	}
    k--;  
}
void Cen(BT T)
{
	int a[100],i=1;
	for(int j=0;j<=100;j++)  //		先全部清零
		a[j]=0;
	ProLeveNum(T ,a);
    cout<<"二叉树的高度是："<<a[0]<<endl;
	while(a[i])
	{
		cout<<"二叉树第"<<i<<"层的节点数为："<<a[i]<<endl;
		i++;
	}
}
	







void windows()   
{

	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.  中序输出                             =\n");
	printf("             =                                              =\n");
	printf("             =     8.  后续输出                             =\n");
	printf("             =                                              =\n");
	printf("             =     0.  退出程序                             =\n");
	printf("             =                                              =");
	printf(" \n             ---------------------------------------------\n");
}

int main()
{
	BT T;
    int choice;
	while(1)       //  进行一个操作后又回到窗口，  是用户选择下一操作！
	{
		//system("cls");
		windows();
		printf("           欢迎简单二叉树操作系统!!请输入您的选择 (0-8): ");//  made by 杨杨
		cin>>choice;
		getchar();
		switch(choice)
		{
			case 1 : system("cls");   CreateBT(T);             break;
			case 2 : system("cls");   Num(T) ;                 break;
			case 3 : system("cls");   HIGH( T);                break;
			case 4 : system("cls");   Serach( T) ;             break;
			case 5 : system("cls");   Cen(T);                  break;
			case 6 : system("cls");   PreOrderT(T);            break;
			case 7 : system("cls");   InOrderT( T);            break;
			case 8 : system("cls");   PostOrderT(T);           break;
			case 0 :                                           break;
			default:system("cls");printf("输入不正确! 请再次输入!!\n");
		}
		if(choice==0)
			break;
	}
	return 0;
}