数据结构实验三

#include<stdio.h>
#include<stdlib.h>
#define Stack_size 100
#define Stackincreament 10
#define MAXQ_size 100
typedef struct Binode{
char data;
struct Binode *lchild,*rchild;
}Binode,*Bitree;
typedef struct{
Bitree *base;
int top;
int stacksize;
}sqstack;
typedef struct{
Bitree *base;
int front;
int rear;
}sqQueue;
int Qfull(sqQueue &Q)
{
if((Q.rear+1)%MAXQ_size==Q.front)
return 1;
return 0;
}
void enQueue(sqQueue &Q,Bitree e)
{
if(Qfull(Q))
exit(0);
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQ_size;
}
void initQueue(sqQueue &Q)
{
Q.base=(Bitree*)malloc(MAXQ_size*sizeof(Binode));
Q.front=Q.rear=0;
}
int Qempty(sqQueue &Q)
{
if(Q.rear==Q.front)
return 1;
return 0;
}
void outQueue(sqQueue &Q,Bitree &e)
{
if(Qempty(Q))
exit(0);
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQ_size;
}
void initstack(sqstack &s)
{
s.base=(Bitree*)malloc(Stack_size*sizeof(Bitree));
s.stacksize=Stack_size;
if(!s.base)
exit(0);
s.top=0;
}
void push(sqstack &s,Bitree e)
{
if(s.top>=s.stacksize)
{
s.base=(Bitree*)realloc(s.base,(Stack_size+Stackincreament)*sizeof(Bitree));
if(!s.base)
exit(0);
s.stacksize+=Stackincreament;
}
s.base[s.top++]=e;
}
void pop(sqstack &s,Bitree &e)
{
if(s.top==0)
return ;
e=s.base[--s.top];
}
void creatBiTree(Bitree &bt)
{
char ch;
ch=getchar();
if(ch=='#')
bt=NULL;
else
{
bt=(Bitree)malloc(sizeof(Binode));
bt->data=ch;
creatBiTree(bt->lchild);
creatBiTree(bt->rchild);
}
}
int stackempty(sqstack &s)
{
if(s.top==0)
return 1;
return 0;
}
Bitree Gettop(sqstack &s,Bitree &e)
{
if(stackempty(s))
exit(0);
e=s.base[s.top-1];
return e;
}
void preorderTraverse1(Bitree &bt)
{
Bitree p;
if(bt)
{
sqstack s;
initstack(s);
push(s,bt);
while(!stackempty(s))
{
while(Gettop(s,p)&&p)
{
printf("%c",p->data);
push(s,p->lchild);
}
pop(s,p);
if(!stackempty(s))
{
pop(s,p);
push(s,p->rchild);
}
}
}
printf("\n");
}
void preorderTraverse2(Bitree bt)
{
if(bt)
{
printf("%c",bt->data);
preorderTraverse2(bt->lchild);
preorderTraverse2(bt->rchild);
}
}
/*void inorderTraverse1(Bitree &bt)
{
if(bt)
{
preorderTraverse1(bt->lchild);
preorderTraverse1(bt->rchild);
}
printf("%c",bt->data);
}*/
void inorderTraverse2(Bitree &bt)
{
Bitree p;
sqstack s;
if(bt)
{
initstack(s);
push(s,bt);
while(!stackempty(s))
{
while(Gettop(s,p)&&p)
push(s,p->lchild);
pop(s,p);
if(!stackempty(s))
{
pop(s,p);
printf("%c",p->data);
push(s,p->rchild);
}
}
}
printf("\n");
}
void leafnum(Bitree bt,int &leaf)
{//用栈实现
sqstack s;
Bitree p;
leaf=0;
if(!bt)
leaf=0;
else
{
initstack(s);
push(s,bt);
while(!stackempty(s))
{
while(Gettop(s,p)&&p)
push(s,p->lchild);
pop(s,p);
Gettop(s,p);
push(s,p->rchild);
if(!Gettop(s,p))
{
pop(s,p);
leaf++;
pop(s,p);
printf("第%d个叶子结点为:%c\n",leaf,p->data);
}
if(!stackempty(s))
{
Gettop(s,p);
pop(s,p);
push(s,p->rchild);
}
}
}
printf("该树的叶子数为:%d,总结点数为:%d\n",leaf,2*leaf-1);
}
void leveltraverse(Bitree bt)
{
sqQueue Q;
Bitree p;
if(bt)
{
initQueue(Q);
enQueue(Q,bt);
while(!Qempty(Q))
{
outQueue(Q,p);
printf("%c",p->data);
if(p->lchild)
enQueue(Q,p->lchild);
if(p->rchild)
enQueue(Q,p->rchild);
}
}
printf("\n");
}
void Depth(Bitree bt,int &depth)
{//二叉树的深度
Bitree p;
sqQueue Q;
int hp,tp,lc;
initQueue(Q);
if(bt)
{
hp=tp=depth=0;
Q.base[tp++]=bt;
lc=tp;
while(hp<tp)
{
p=Q.base[hp++];
if(p->lchild)
Q.base[tp++]=p->lchild;
if(p->rchild)
Q.base[tp++]=p->rchild;
if(lc==hp)
{
depth++;
lc=tp;
}
}
}
printf("该树的高度为:%d\n",depth);
}
int judge(Bitree bt)
{//判断是否为完全二叉树
int flag=0;
Bitree p;
sqQueue Q;
if(!bt)
return 1;
initQueue(Q);
enQueue(Q,bt);
while(!Qempty(Q))
{
outQueue(Q,p);
if(p->lchild&&!flag)
enQueue(Q,p->lchild);
else if(p->lchild)
return 0;
else
flag=1;
if(p->rchild&&!flag)
enQueue(Q,p->rchild);
else if(p->rchild)
return 0;
else
flag=1;
}
return 1;
}
void storage(Bitree bt)
{//将二叉树结点存入一维数组
char a[100];
int i=1,k=1;
int Q1[100],front=0,rear=0;
Bitree p;
sqQueue Q;
for(i=1;i<=100;i++)
a[i]='#';
if(!bt)
return;
else{
initQueue(Q);
enQueue(Q,bt);
Q1[rear++]=k;
while(!Qempty(Q))
{
outQueue(Q,p);
k=Q1[front++];
a[k]=p->data;
if(p->lchild)
{
enQueue(Q,p->lchild);
Q1[rear++]=2*k;
}
if(p->rchild)
{
enQueue(Q,p->rchild);
Q1[rear++]=2*k+1;
}
}
}
for(int j=1;j<=front;j++)
printf("%5c",a[j]);
printf("\n");
}
int main()
{
printf("请输入完全二叉树的先序序列:\n");
int leaf,depth;
Bitree bt;
creatBiTree(bt);
preorderTraverse1(bt);
preorderTraverse2(bt);
printf("\n");
inorderTraverse2(bt);
leveltraverse(bt);
leafnum(bt,leaf);
Depth(bt,depth);
if(judge(bt))
printf("该树为完全二叉树.\n");
else
printf("该树不是完全二叉树.\n");
storage(bt);
return 0;
}