#include "stdio.h"
#include "malloc.h"
typedef char ElemType;
typedef struct node {
ElemType data;
struct node* lchild;
struct node* rchild;
} BTNode;
typedef struct {
BTNode *data[1000];
int top;
} SqStack;
void InitStack(SqStack *&s) {
s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1;
}
bool StackEmpty(SqStack *s) {
return(s->top==-1);
}
bool Push(SqStack *&s,BTNode *e) {
if(s->top==199) {
return false;
}
s->top++;
s->data[s->top]=e;
return true;
}
bool Pop(SqStack *&s,BTNode *e) {
if(s->top==-1) {
return false;
}
e=s->data[s->top];
s->top--;
return true;
}
bool GetTop(SqStack *&s,BTNode *e) {
if(s->top==-1) {
return false;
}
e=s->data[s->top];
return true;
}
void DestroyStack(SqStack *&s) {
free(s);
}
BTNode * Create() { //创建二叉树
BTNode *root;
char ch;
scanf("%c",&ch);
if(ch=='#') root==NULL;
else {
printf("%c",ch);
root=(BTNode *)malloc(sizeof(BTNode));
root->data=ch;
root->lchild=Create();
root->rchild=Create();
}
return root;
}
void Count(BTNode *p,int i) { //求二叉树的最大宽度
BTNode *q[20];
int front=0;
int rear=0;
int count=0;
int k=0;
if(p) {
rear++;
q[rear]=p;
count++;
}
for(int n=2; n<=i; n++) {
for(int m=0; m<=count; m++) {
front++;
p=q[front];
count--;
if(p->lchild!=NULL) {
rear++;
q[rear]=p->lchild;
count++;
}
if(p->rchild!=NULL) {
rear++;
q[rear]=p->rchild;
count++;
}
}
if(k
k=count;
printf("该二叉树的最大宽度为:%d",k);
}
}
}
void PostOrder(BTNode *&b) {
SqStack *st;
InitStack(st);
BTNode *p=b;
BTNode *r=NULL;
while(p!=NULL||!StackEmpty(st)) {
if(p!=NULL) {
Push(st,p);
p=p->lchild;
} else {
GetTop(st,p);
if(p->rchild&&p->rchild!=r) {
p=p->rchild;
} else {
Pop(st,p);
printf("%c",p->data);
r=p;
p=NULL;
}
}
}
}
int main() {
BTNode *b;
int i;
b=Create();
scanf("%d",&i);
Count(b,i);
PostOrder(b);
}
主函数调用postorder函数不运行