二叉树.cpp

数据结构

#include <stdio.h> 
#include <stdlib.h> 

 
typedef char DataType; /*设数据域类型为字符型*/ 
typedef struct node{ 
	DataType data; 
	struct node *lchild,*rchild; /*左右链域为指向结点结构的指针类型*/ 
}BinTNode,*BinTree; /*结点类型*/ 

BinTree CreateBinTree() 
{/*以加入结点的先序序列输入，构造二叉链表*/ 
	char ch; 
	scanf("\n%c",&ch); 
	if (ch=='0') return NULL; /*读入0时，将相应结点置空*/ 
	else 
	{ 
		BinTree T=(BinTNode*)malloc(sizeof(BinTNode)); /*生成结点空间*/ 
		T->data=ch; 
		T->lchild=CreateBinTree(); /*构造二叉树的左子树*/ 
		T->rchild=CreateBinTree(); /*构造二叉树的右子树*/ 
		return T; 
	} 


}
void Inorder(BinTree T) 
{/*中序遍历二叉树T*/ 
	if (T) 
	{ 
		Inorder(T->lchild); /*中序遍历二叉树的左子树*/ 
		printf("%3c",T->data); /*访问结点的数据*/ 
		Inorder(T->rchild); /*中序遍历二叉树的右子树*/ 
	}  
} 
void Preorder(BinTree T)
{
	if (T) 
	{   printf("%3c",T->data); /*访问结点的数据*/ 
		Preorder(T->lchild); /*前序遍历二叉树的左子树*/ 
		Preorder(T->rchild); /*前序遍历二叉树的右子树*/ 
	} 
}

void Postorder(BinTree T)
{
	if (T) 
	{   printf("%3c",T->data); /*访问结点的数据*/ 
	Postorder(T->lchild); /*前序遍历二叉树的左子树*/ 
	Postorder(T->rchild); /*前序遍历二叉树的右子树*/ 
	} 

}

int LevNumber(BinTree T) //求二叉树的叶子结点 
{ 
	if(T== NULL) 
	{
		return 0; 
	} 
	else if(T->lchild == NULL&&T->rchild == NULL)
	{ 
		return 1;
	} 
	else 
	{ 
		return LevNumber(T->lchild)+LevNumber(T->rchild);
	} 
}


int DepBinTree(BinTree T)//求深度
{   int max=0;
	if (T==NULL)
	 return 0;
	else if (T->lchild==0&&T->rchild==0)
	 return 1;
	else 
	{if(DepBinTree(T->lchild)>DepBinTree(T->rchild)) 
	  max=DepBinTree(T->lchild);
	else max=DepBinTree(T->rchild);
	 return 1+max;
	}
}

void main() 
{ 
	BinTree T; 
	char ch1,ch2; int count=0,number=0;
	
	printf("\n欢迎进入二叉树基本操作测试程序，请选择：\n"); 
	ch1='y'; 
	printf("\nA二叉树建立 \nB 先序遍历 \nC 中序遍历"); 
	printf("\nB 先序遍历");
	printf("\nC 中序遍历");
	printf("\nD 后序遍历");
	printf("\nE 深度");
	printf("\nF 求叶子数");
	printf("\nG 退出\n ");

	while(ch1=='y' || ch1=='Y') 
	{   scanf("\n%c",&ch2); 
		switch(ch2) 
		{ 
		case 'a': 
		case 'A': 
			printf("请按带空指针的二叉树先序遍历输入建立二叉树存储的结点序列:\n"); 
		T=CreateBinTree(); 
            if (T!=0) printf("二叉树已经建立\n");
			break; 
		case 'b': 
		case 'B': 
			printf("该二叉树的前序遍历序列为:\n"); 
			Preorder(T);
			printf("\n"); 
			break; 
		case 'c': 
		case 'C': 
			printf("该二叉树的中遍历序列为:\n"); 
			Inorder(T);
			printf("\n"); 
			break; 
		case 'd': 
		case 'D': 
			printf("该二叉树的后遍历序列为:\n"); 
			Postorder(T); 
			printf("\n"); 
			break; 
		case 'e':
		case 'E':
			count=DepBinTree(T);
	        printf("该二叉树深度为%d",count); 
            printf("\n"); 
			break; 
		case 'f': 
		case 'F': 
		count=LevNumber(T); /*count初值为0,用于统计叶结点数目*/ 
			printf("该二叉树有%d个叶子。\n",count); 
			break; 
	
		case 'g': 
		case 'G': 
			ch1='n'; 
			break; 
		default:ch1='n'; 
			
		} 
	} 
}