学步园

数据结构   二叉数的建立与遍历

递归方式遍历及基本操作

#include<stdio.h>
#include<malloc.h>
#define OVERFLOW 0;
#define ERROR O;
#define OK 1;
typedef char TElemType;
typedef int Status;
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree &T)
{
	char ch;
	fflush(stdin); 
	scanf("%c",&ch); 
	fflush(stdin); 
	if(ch==' ')T=NULL;
	else{		
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))return OVERFLOW;
		T->data=ch;
		printf("请输入 %c 的左节点：\n",T->data);
		CreateBiTree(T->lchild);
		printf("请输入 %c 的右节点：\n",T->data);
		CreateBiTree(T->rchild);
	}
}
Status PreOrderTraver(BiTree T,Status(*Visit)(TElemType))//先序遍历 
{
	 if(T)
	 {
		  Visit(T->data);
		  PreOrderTraver(T->lchild,Visit);
		  PreOrderTraver(T->rchild,Visit);
	 }
}
Status InOrderTraverse(BiTree &T,Status(*Visit)(TElemType))//中序遍历 
{
	 if(T)
	 {
		  InOrderTraverse(T->lchild,Visit);
		  Visit(T->data);
		  InOrderTraverse(T->rchild,Visit); 
	 }
}
Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType))//后序遍历 
{
	 if(T)
	 {
        PostOrderTraverse(T->lchild,Visit);
        PostOrderTraverse(T->rchild,Visit);
        Visit(T->data);
	 }
}
//求叶子数
int leafCount(BiTree T)
{
	int count1,count2;
	if(T==NULL)
		return 0;
	else
	{
		if(T->lchild==NULL&&T->rchild==NULL)
			return 1;
		else
		{
			count1=leafCount(T->lchild);
			count2=leafCount(T->rchild);
			return count1+count2;
		}
	}
}
//***********************************************************************
//求二叉树每层节点的个数,保存到数组num中
void levelCount(BiTree T,int l,int num[])
{
	if(T)
	{
		num[l]++;
		levelCount(T->lchild,l+1,num);
		levelCount(T->rchild,l+1,num);
	}
}
//***********************************************************************
//求二叉树的高度
Status heightTree(BiTree T)
{
	int h1,h2;
	if(T==NULL)
		return 0;
	else
	{
		h1=heightTree(T->lchild);
		h2=heightTree(T->rchild);
		if(h1>h2)return h1+1;
		else return h2+1;
	}
}
Status PrintElement(TElemType e)
{
	printf("%c ",e);
	return OK;
}
int main()
{
	BiTree T;
	printf("请输入树根：\n"); 
	CreateBiTree(T);
	printf("先序遍历：\n");
	PreOrderTraver(T,PrintElement);
	printf("\n中序遍历:\n");
	InOrderTraverse(T,PrintElement);
	printf("\n后序遍历:\n");
	PostOrderTraverse(T,PrintElement);
	printf("\n该树的深度是：%d \n",heightTree(T));
}