#include<stdio.h>
#include<stdlib.h>
#define stackinitsize 100
#define stackincrement 10
#define max 100
///二叉树的类型定义
typedef struct bitnode
{
char data;
struct bitnode *lchild,*rchild;
}bitnode,*bitree;
///栈的类型定义
typedef struct
{
bitree *base;
int top;
int stacksize;
}sqstack;
///队列的类型定义
typedef struct{
bitree *base;
int front,rear;
}cqqueue;
///初始化栈
void initstack(sqstack &S){
S.base=(bitree*)malloc(stackinitsize*sizeof(bitree));
if(!S.base)
return ;
S.top=0;
S.stacksize=stackinitsize;
}
///判空
int stackempty(sqstack S){
if(S.top==0)
return 1;
return 0;
}
///入栈
void push(sqstack &S,bitree e){
S.base[S.top++]= e;
}
///出栈
void pop(sqstack &S,bitree &e){
if(S.top==0){
return ;
}
e=S.base[--S.top];
}
bitree gettop(sqstack &S,bitree &e){
e=S.base[S.top-1];
return S.base[S.top-1];
}
///建队列
void initqueue(cqqueue &Q){
Q.base=(bitree*)malloc(max*sizeof(bitree));
if(!Q.base)
return;
Q.front=Q.rear=0;
}
///判空
int Queueempty(cqqueue Q){
if(Q.rear==Q.front)
return 1;
return 0;
}
///入队列
void enqueue(cqqueue &Q,bitree e){
if((Q.rear+1)%max==Q.front)
return;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%max;
}
///出队列
void dequeue(cqqueue &Q,bitree &e){
if(Q.rear==Q.front)
return;
e=Q.base[Q.front];
Q.front=(Q.front+1)%max;
}
///建立二叉链表
void creatbitree(bitree &bt){
char ch;
ch=getchar();
if(ch=='#')
bt=NULL;
else{
if(!(bt=(bitnode*)malloc(sizeof(bitnode))))
return;
bt->data=ch;
creatbitree(bt->lchild);
creatbitree(bt->rchild);
}
}
///输出
void visit(char b){
printf("%c ",b);
}
///递归遍历算法--先序
void preordertraversexianxu(bitree bt){
if(bt){
visit(bt->data);
preordertraversexianxu(bt->lchild);
preordertraversexianxu(bt->rchild);
}
}
///递归遍历算法——中序
void preordertraversezhongxu(bitree bt){
if(bt){
preordertraversezhongxu(bt->lchild);
visit(bt->data);
preordertraversezhongxu(bt->rchild);
}
}
///递归遍历算法——后序
void preordertraversehouxu(bitree bt){
if(bt){
preordertraversehouxu(bt->lchild);
preordertraversehouxu(bt->rchild);
visit(bt->data);
}
}
///二叉链表存储的层次遍历
void levetraverse(bitree bt){
if(bt){
bitree p;
cqqueue Q;
initqueue(Q);
enqueue(Q,bt);
while(!Queueempty(Q)){
dequeue(Q,p);
visit(p->data);
if(p->lchild) enqueue(Q,p->lchild);
if(p->rchild) enqueue(Q,p->rchild);
}
}
}
///求叶子节点总数
void countleaf(bitree bt,int &leaves){
if(bt){
countleaf(bt->lchild,leaves);
if(!bt->lchild && !bt->rchild)
leaves++;
countleaf(bt->rchild,leaves);
}
}
///求二叉树的节点总数
int Count(bitree bt)
{
if(bt==NULL)
return 0; //空二叉树结点数为0
else //左右子树结点总数加1
return Count(bt->lchild)+Count(bt->rchild)+1;
}
///bt的深度
int bitreedepth(bitree bt){
int depthl,depthr;
if(bt==NULL)
return 0;
else{
depthl=bitreedepth(bt->lchild);
depthr=bitreedepth(bt->rchild);
if(depthl>=depthr)
return depthl+1;
else
return depthr+1;
}
}
int main()
{
int leaf=0,depth;
bitree bt; ///建树
creatbitree(bt);
printf("递归遍历的结果-先序：");
preordertraversexianxu(bt);///递归遍历
printf("\n递归遍历的结果-中序：");
preordertraversezhongxu(bt);///递归遍历
printf("\n递归遍历的结果-后序：");
preordertraversehouxu(bt);///递归遍历
printf("\n层次遍历结果：");
levetraverse(bt);///层次遍历
printf("\n");
printf("二叉树的节点总数：%d\n",Count(bt));
countleaf(bt,leaf);///叶子节点总数
printf("叶子节点总数 %d\n",leaf);
}
