二叉树的建立，遍历等基本操作代码,C代码库,德仔网

代码语言
代码分类
【C】二叉树的建立，遍历等基本操作
作者:Dezai.CN / 发布于2013/7/30/ 988

	/**********************************************************************
	* Description:先序创建二叉树,遍历等操作
	* Author:099074345
	* Datetime:2011-4-21 21:54
	* Compile Environment:windowsXP sp3+VC6.0
	**********************************************************************/

	#include "stdio.h"
	#include "stdlib.h"

	//*********************************************************************
	//定义二叉树的结构
	typedef struct tree{
	 char data;
	 struct tree *lchild;
	 struct tree *rchild;
	}*Ptree,Dtree;

	//*********************************************************************
	//先序创建二叉树
	Ptree createTree()
	{
	 char ch;
	 Ptree t;
	 ch=getchar();
	 if(ch=='#')
	 t=NULL;
	 else
	 {
	 t=(Ptree)malloc(sizeof(Dtree));
	 t->data=ch;
	 t->lchild=createTree();
	 t->rchild=createTree();
	 }
	 return t;
	}
	//***********************************************************************
	//定义队列
	typedef struct queue_{
	 Ptree data[100];
	 int front,rear;
	}Dqueue,*Pqueue;
	//***********************************************************************
	//初始化队列
	Pqueue initQueue()
	{
	 Pqueue p;
	 p=(Pqueue)malloc(sizeof(Dqueue));
	 if(p)
	 {
	 p->front=0;
	 p->rear=0;
	 }
	 return p;
	}
	//***********************************************************************
	//判断队列是否为空
	int emptyQueue(Pqueue p)
	{
	 if(p->front==p->rear)
	 return 1;
	 else
	 return 0;
	}
	//***********************************************************************
	//入队
	void inQueue(Pqueue p,Ptree t)
	{
	 p->rear=(p->rear+1)%100;
	 p->data[p->rear]=t;
	}
	//***********************************************************************
	//出队
	void outQueue(Pqueue p,Ptree* t)
	{
	 p->front=(p->front+1)%100;
	 *t=p->data[p->front];
	}
	//***********************************************************************
	//层次遍历
	void levelOrder(Ptree t)
	{
	 Ptree p=t;
	 Pqueue Q;
	 if(p)
	 {
	 Q=initQueue();//初始化队列
	 printf("%c",p->data);
	 inQueue(Q,p);
	 while(!emptyQueue(Q))//当队列不为空
	 {
	 outQueue(Q,&p);//出队
	 if(p->lchild)
	 {
	 printf("%c",p->lchild->data);
	 inQueue(Q,p->lchild);//进队
	 }
	 if(p->rchild)
	 {
	 printf("%c",p->rchild->data);
	 inQueue(Q,p->rchild);//进队
	 }
	 }
	 }
	}
	//*********************************************************************
	//先序遍历
	void preOrder(Ptree t)
	{
	 if(t)
	 {
	 printf("%c",t->data);
	 preOrder(t->lchild);
	 preOrder(t->rchild);
	 }
	}

	//***********************************************************************
	//中序遍历
	void intOrder(Ptree t)
	{
	 if(t)
	 {
	 intOrder(t->lchild);
	 printf("%c",t->data);
	 intOrder(t->rchild);
	 }
	}

	//***********************************************************************
	//后序遍历
	void postOrder(Ptree t)
	{
	 if(t)
	 {
	 postOrder(t->lchild);
	 postOrder(t->rchild);
	 printf("%c",t->data);
	 }
	}
	//***********************************************************************
	//求叶子数
	int leafCount(Ptree 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(Ptree t,int l,int num[])
	{
	 if(t)
	 {
	 num[l]++;
	 levelCount(t->lchild,l+1,num);
	 levelCount(t->rchild,l+1,num);
	 }
	}
	//***********************************************************************
	//求二叉树的高度
	int heightTree(Ptree 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;
	 }
	}
	//*********************************************************************
	//主函数
	int main()
	{
	 int num[10]={0};
	 int height;
	 int i;
	 Ptree t;

	 t=createTree();//先序创建二叉树

	 printf("后序遍历");//后续遍历
	 postOrder(t);
	 printf("\n");

	 printf("层次遍历");//层次遍历
	 levelOrder(t);
	 printf("\n");

	 height=heightTree(t);//数的深度
	 printf("深度:%d\n",height);

	 levelCount(t,1,num);//每层节点数
	 for(i=1;i<=height;i++)
	 printf("第%d层个数:%d\n",i,num[i]);

	 printf("叶子总数:%d\n",leafCount(t));//叶子数
	 return 0;
	}
试试其它关键字
　二叉树　
同语言下
可能有用的
Dezai.CN贡献的其它代码(4037)