cpp1.cpp

一个比较完整的二叉树系统,可以对学习数据结构中的二叉树应该有一个比较理想的直观的了解吧

#include "stdio.h"
#include "stdlib.h"
#define Maxsize 100;
typedef int ElemType;
typedef struct BT 
{
	ElemType data;
	struct BT *lch,*rch;
}BT;


BT*CreatBT();
void preorder(BT *T);
void inorder(BT *T);
void postorder(BT *T);
void leafnum(BT *T);
void ShowTree(BT *T);
void Nodenum(BT*T);


void main()
{
	 BT *T=NULL;
	 //char ch1;
	 int choice;
	 //char x;
	 //ch1='y';
	 //while(ch1=='y'||ch1=='Y')
	 do{
		 printf("\n");
		 printf("      实验5 二叉树子系统      \n\n");
		 printf("   ****************************");
		 printf("\n   *                         *\n");
		 printf("\n   *        主菜单           *\n");
		 printf("\n   *    1 建立二叉树         *\n");
		 printf("\n   *    2 先序遍历二叉树     *\n"); 
		 printf("\n   *    3 中序遍历二叉树     *\n");
         printf("\n   *    4 后序遍历二叉树     *\n");
         printf("\n   *    5 二叉树的叶子结点数 *\n");
		 printf("\n   *    6 凹入显示二叉树     *\n");
		 printf("\n   *    7 二叉树的所有结点数 *\n");
		 printf("\n   *    8 退出程序运行       *\n");
		 printf("   ****************************");
		 printf("\n   请输入您的选择（1，2，3，4，5，6，7，8): ");
		 scanf("%d",&choice);
		 if(choice==1)
		 {
			printf("\n二叉树的建立，以输入“0”表示结束：！\n");
			printf("\n请输入根结点：");
		    T=CreatBT();
			printf("二叉树成功建立");
		 }
		 else if(choice==2)
		 {
			 printf("\n先序遍历二叉树 :");
			 preorder(T);
		 }
		 else if(choice==3)
		 {
			 printf("\n 中序遍历二叉树:");
			 inorder(T);
		 }
		 else if(choice==4)
		 { 
			 printf("\n");
			 printf("  后序遍历二叉树 : ");
			 postorder(T);
		 }
		 else if(choice==5)
		 {
			 printf("\n");
			 printf(" 二叉树的叶子结点数为 : ");
			 leafnum(T);
		 }
		 else if(choice==6)
			 ShowTree(T);
		 else if(choice==7)
		 {
		 	 int count=0;Nodenum(T);
		     printf("\n该二叉树总共有%d个结点。\n",count);
		 }
		 else if(choice==8)
		 	 exit(0);
	 
	 }while(choice<=8);
}/*main end*/ 


BT*CreatBT()    //建立二叉树
{
	BT *t;
	int x;
	scanf("%d",&x);
	//getchar();
	if(x==0) 
	{
		t=NULL;
	    exit;
	}
	else
	{
		t=new BT;//(BT*)malloc(sizeof(BT));
		t->data=x;
		printf("\n请输入%d结点的左子结点:",t->data );
		t->lch=CreatBT();
		printf("\n请输入%d结点的右子结点:",t->data );
		t->rch=CreatBT();
	}
	return t;
}


void preorder(BT *T)
{
	if(T==NULL) return;
	else
	{
		printf("%3d",T->data);
		preorder(T->lch );
		preorder(T->rch);
	}
}

void inorder(BT *T)
{
	if(T==NULL) return;
	else
	{
		inorder(T->lch );
		printf("%3d",T->data);
		inorder(T->rch);
	}
}

void postorder(BT *T)
{	
	if(T==NULL) return;
	else
	{
		postorder(T->lch );
		postorder(T->rch);
		printf("%3d",T->data);
	}
}

void leafnum(BT *T)
{
	int count=0;
	if(T)
	{
		if(T->lch==NULL&&T->rch==NULL)
			count++;
		leafnum(T->lch );
		leafnum(T->rch );
	}
	printf("%d",count);
}

void ShowTree(BT *T)    //按凹入法显示二叉树
{
	BT *stack[100];
	BT*p;
	int level[100][2];
	int top,n,i;
	int width=4;
	if(T!=NULL)
	{
		printf("\n二叉树的凹入表示法f:\n");
		top=1;
		stack[top]=T;
		level[top][0]=width;
		while(top>0)
		{
			p=stack[top];
			n=level[top][0];
			for(i=1;i<=n;i++)
				printf(" ");
			printf("%d",p->data);
			for(i=n+1;i<60;i+=2)
				printf("一");
			printf("\n\t\t");
			top--;
			if(p->rch!=NULL)
			{
				top++;
				stack[top]=p->rch ;
				level[top][0]=n+width;
				level[top][1]=2;
			}
			if(p->lch!=NULL)
			{
				top++;
				stack[top]=p->lch ;
				level[top][0]=n+width;
				level[top][1]=1;
			}
		}
	}
}

void Nodenum(BT*T)
{
	int count=0;
	if(T) count++;
	Nodenum(T->lch );
	Nodenum(T->rch );
}