sy3.cpp

二叉树的基本操作

#include <malloc.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h> //exit()

#define OK 1
#define NULL 0
#define FALSE 0

typedef struct BiTNode{ //定义链式二叉树结构体
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree T;
char ch;
int flag=0;

int createBiTree(BiTree &T){
	//按先序输入二叉树中结点的值（一个字符），空格表示空树
	ch=getchar();
	if(ch==' ')T=NULL; //表示空树
	else if(ch==10)flag=1;  //结点信息输入错误则返回0
	else {
		T=(BiTNode*)malloc(sizeof(BiTree));
		if(!T)exit(1);//空间分配不成功则退出
		T->data=ch;                //生成根结点
		createBiTree(T->lchild);   //生成左子树
		createBiTree(T->rchild);   //生成右子树
	}//else
	return OK;
}//createBiTree

int PreOrderTraverse(BiTree T){   //先序遍历二叉树的递归算法
	if(T){
		printf("%c",T->data);        //访问根结点
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}//if
	return OK;
}

int InOrderTraverse(BiTree T){   //中序
	if(T){
		InOrderTraverse(T->lchild);
		printf("%c",T->data);        //访问根结点
		InOrderTraverse(T->rchild);
	}//if
	return OK;
}

int PostOrderTraverse(BiTree T){ // 后序
	if(T){
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		printf("%c",T->data);        //访问根结点
	}
	return OK;
}

int NodeCount(BiTree T){ //
    if(T==NULL) return 0;// 如果是空树，则结点个数为0
    else return 1+NodeCount(T->lchild)+NodeCount(T->rchild);
//否则结点个数为1+左子树的结点个数+右子树的结点个数
}

int LeafNodeCount(BiTree T ){
	if(!T)return 0; //如果是空树，则叶子个数为0; 
	else if(LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild)==0)return 1;//如果是叶子结点，则叶子结点个数为1
	else return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);
        //否则叶结点个数为左子树的叶结点个数+右子树的叶结点个数
} 


int  Depth(BiTree T){//计算二叉树的深度
	int m,n;
	if(T==NULL )return 0;//如果是空树，则深度为0
	else {
		m=Depth(T->lchild);//计算左子树的深度记为m
		n=Depth(T->rchild);//计算右左子树的深度记为n
		if(m>n) return(m+1);//二叉树的深度为m 与n的较大者加1
		else  return (n+1);
	}
}

void main(){
	int no,out=1;
	char choose;
//*****************************主界面**********************************
	while(out){
		system("cls");
		printf("\n这是实验3的程序，请按照说明使用：\n");
		printf("1．以二叉链表表示二叉树，建立一棵二叉树，请输入1");
		printf("\n2．输出二叉树的前序遍历结果，请输入2");
		printf("\n3．输出二叉树的中序遍历结果，请输入3");
		printf("\n4．输出二叉树的后序遍历结果请输入4");
		printf("\n5．统计二叉树的结点个数，请输入5");
		printf("\n6．统计二叉树的叶结点个数，请输入6");
		printf("\n7．计算二叉树的深度，请输入7");
		printf("\n8．退出，请输入其他\n");
//********************处理输入的选项************************************
	choose=getch();
	switch(choose){
		case '1':
			system("cls");
			printf("\n请输入二叉链表各结点信息建立二叉树，空树用空格表示：\n");
			if(createBiTree(T)==0||flag==1){   //结点输入错误！
				printf("输入错误，请重新输入结点信息!\n"); 
				getch();break;}
			else
			printf("输入完毕！");//成功建立二叉链表
			getch();break;
		case '2':
			printf("\n先序遍历的结果是：");
			PreOrderTraverse(T);
			getch();break;
		case '3':
			printf("\n中序遍历的结果是：");
			InOrderTraverse(T);
			getch();break;
		case '4':
			printf("\n后序遍历的结果是：");
			PostOrderTraverse(T);
			getch();break;
		case '5':
			no=NodeCount(T);
			printf("\n总结点个数为:%d\n",no);
			getch();break;
		case '6': 
			printf("\n叶子结点的个数为:%d\n",LeafNodeCount(T));
			getch();break;
		case '7': 
			printf("\n二叉树深度为：%d\n",Depth(T));
			getch();break;
		default :
			printf("\n你输入的是:其他\n");
			getch();
			out=0;
		} //end switch
	}//end of while
	system("cls");
	printf("\n\n\t\t欢迎使用，再见！");
}