- /**********************************************************************
- * Description:先序创建二叉树,遍历等操作
- * 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;
- }
- //该片段来自于http://www.codesnippet.cn/detail/230120131894.html
来源: http://www.codesnippet.cn/detail/230120131894.html