# 后序遍历二叉树

``````2
1 -1
1 2 0 3 4 -1
``````

``````1 1
3 3 4 2 1
``````

``````#include<stdio.h>
#include<stdlib.h>

#define maxsize 20

typedef struct node
{
int ltag,rtag;
int data;
struct node *lch,*rch;
}btnode;

btnode *Q[maxsize];

int flag;

btnode *creat()
{
int c;
int front,rear;
btnode *T,*S;
T=NULL;
front=1;rear=0;
scanf("%d",&c);
while(c!=-1)
{
S=NULL;
if(c!=0)
{
S=(btnode *)malloc(sizeof(btnode));
S->data=c;
S->lch=NULL;
S->rch=NULL;
S->rtag=0;
S->ltag=0;
}
rear++;
Q[rear]=S;
if(rear==1) T=S;
else
{
if(S!=NULL && Q[front]!=NULL)
if(rear%2==0) Q[front]->lch=S;
else Q[front]->rch=S;
if(rear%2==1) front++;
}
scanf("%d",&c);
}
return T;
}

void pre(btnode *T)
{
if(T)
{
if(T->ltag!=1) pre(T->lch);

if(T->rtag!=1) pre(T->rch);
if(flag)
{
printf(" ");
}
flag=1; printf("%d",T->data);
}
}
int depth(btnode *bt)
{
int m,n;
if(bt==NULL)
return 0;
m=depth(bt->lch);
n=depth(bt->rch);
if(m>n)
return m+1;
else
return n+1;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
flag=0;
btnode *bt;
bt=creat();
printf("%d ",depth(bt));
pre(bt);
printf("\n");
}
return 0;
}
``````

``````#include<stdio.h>
#include<stdlib.h>

#define maxsize 20

typedef struct node
{
int ltag,rtag;
int data;
struct node *lch,*rch;
}btnode;

btnode *Q[maxsize];

int flag;

btnode *creat()
{
int c;
int front,rear;
btnode *T,*S;
T=NULL;
front=1;rear=0;
scanf("%d",&c);
while(c!=-1)
{
S=NULL;
if(c!=0)
{
S=(btnode *)malloc(sizeof(btnode));
S->data=c;
S->lch=NULL;
S->rch=NULL;
S->rtag=0;
S->ltag=0;
}
rear++;
Q[rear]=S;
if(rear==1) T=S;
else
{
if(S!=NULL && Q[front]!=NULL)
if(rear%2==0) Q[front]->lch=S;
else Q[front]->rch=S;
if(rear%2==1) front++;
}
scanf("%d",&c);
}
return T;
}

void pre(btnode *T)
{
if(T)
{
if(T->ltag!=1) pre(T->lch);

if(T->rtag!=1) pre(T->rch);
if(flag)
{
printf(" ");
}
flag=1; printf("%d",T->data);
}
}
int depth(btnode *bt)
{
int m,n;
if(bt==NULL)
return 0;
m=depth(bt->lch);
n=depth(bt->rch);
if(m>n)
return m+1;
else
return n+1;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
flag=0;
btnode *bt;
bt=creat();
printf("%d ",depth(bt));
pre(bt);
printf("\n");
}
return 0;
}
``````