二叉树的先序，中序，和后序遍历用静态和动态两种方法实现

92 阅读 0 评论 61 点赞

我是靠谱客的博主畅快西装，最近开发中收集的这篇文章主要介绍二叉树的先序，中序，和后序遍历用静态和动态两种方法实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

给出一个数字N( 0<= N <= 20)按中序遍历1~2^N-1 建立一棵二叉树.然后有M次询问,然后有三种询问操作:1代表先序遍历,2代表中序遍历,3代表后序遍历.

Input

多组测试数据,每组第一行给出N

第二行一个M( M < 10 )

下面跟M行

每行一个数字(1,2,3)每个数字对应着一个操作

Output

对于每个询问操作,请输出结果,每次询问一行(每行最后没有多余的空格,如果一行没有数字则为空行)

Sample Input

4212

Sample Output

8 4 2 1 3 6 5 7 12 10 9 11 14 13 151 2 3 4 5 6 7 8 9 10 11 12 13 14 15

HINT

//一开始给tree赋值为-1，用ree[id]==-1来作为返回条件的，但tree开的太大
//赋值占用很长时间会超时，考虑到这里是满二叉树，所以用树的深度depth来作为返回条件
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
int tree[10000000];
int data[10000000];
int p,N,flag;
void build(int id){ //这里是中序建立，若是先序和后序，就把 tree[id]=data[p++]的位置改下即可
if(id*2<pow(2,N))
build(id*2);
tree[id]=data[p++];
if(id*2+1<pow(2,N))
build(id*2+1);
}
void PreOrderOutput(int id,int depth){
if(depth>N)
return ;
else{
if(flag){
cout<<tree[id];
flag=false;
}
else
cout<<" "<<tree[id];
PreOrderOutput(id*2,depth+1);
PreOrderOutput(id*2+1,depth+1);
}
}
void InOrderOutput(int id,int depth){
if(depth>N)
return ;
else{
InOrderOutput(id*2,depth+1);
if(flag){
cout<<tree[id];
flag=false;
}
else
cout<<" "<<tree[id];
InOrderOutput(id*2+1,depth+1);
}
}
void PostOrderOutput(int id,int depth){
if(depth>N)
return ;
else{
PostOrderOutput(id*2,depth+1);
PostOrderOutput(id*2+1,depth+1);
if(flag){
cout<<tree[id];
flag=false;
}
else
cout<<" "<<tree[id];
}
}
int main(){
int M,select;
while(scanf("%d",&N)==1){
for(int i=1;i<pow(2,N);i++)
data[i]=i;
// memset(tree,-1,sizeof(tree));
p=1;
build(1);
scanf("%d",&M);
while(M--){
scanf("%d",&select);
if(N==0){
cout<<endl;
continue;
}
flag=true;
switch(select){
case 1:PreOrderOutput(1,1); cout<<endl;break;
case 2:InOrderOutput(1,1); cout<<endl;break;
case 3:PostOrderOutput(1,1);cout<<endl;break;
}

}
}

//system("pause");
return 0;
}

上面的代码用了700多ms，其实还可以优化，改了一下只用了200多ms

printf 比 cout 快，库函数pow最好自己写一个，另外JJ一下，下面我把pow[i-1]*2 写成pow[i-1]+pow[i-1] 也会快一点点，嘿嘿

#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
int tree[10000000];
int data[10000000];
int POW[30];
int p,N,flag;
void build(int id){
if(id*2<POW[N])
build(id*2);
tree[id]=data[p++];
if(id*2+1<POW[N])
build(id*2+1);
}
void PreOrderOutput(int id,int depth){
if(depth>N)
return ;
else{
if(flag){
printf("%d",tree[id]);
flag=false;
}
else
printf(" %d",tree[id]);
PreOrderOutput(id*2,depth+1);
PreOrderOutput(id*2+1,depth+1);
}
}
void InOrderOutput(int id,int depth){
if(depth>N)
return ;
else{
InOrderOutput(id*2,depth+1);
if(flag){
printf("%d",tree[id]);
flag=false;
}
else
printf(" %d",tree[id]);
InOrderOutput(id*2+1,depth+1);
}
}
void PostOrderOutput(int id,int depth){
if(depth>N)
return ;
else{
PostOrderOutput(id*2,depth+1);
PostOrderOutput(id*2+1,depth+1);
if(flag){
printf("%d",tree[id]);
flag=false;
}
else
printf(" %d",tree[id]);
}
}
int main(){
POW[0] = 1;
for( int i = 1; i < 30; ++i )
POW[i] = POW[i-1] + POW[i-1];
int M,select;
while(scanf("%d",&N)==1){
for(int i=1;i<POW[N];i++)
data[i]=i;
// memset(tree,-1,sizeof(tree));
p=1;
build(1);
scanf("%d",&M);
while(M--){
scanf("%d",&select);
if(N==0){
printf("n");
continue;
}
flag=true;
switch(select){
case 1:PreOrderOutput(1,1); printf("n");break;
case 2:InOrderOutput(1,1); printf("n");break;
case 3:PostOrderOutput(1,1);printf("n");break;
}

}
}

//system("pause");
return 0;
}

静态的比动态的快，但链表看起来更有技术含量一点，呵呵，所以我还是写了个动态的。如下，时效是700多ms

#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
typedef struct BitNode{
int data;
struct BitNode *lchild,*rchild;
}BitNode,*BitTree;
int N;
bool flag;
int data[1050000],p;
int POW[30];
BitTree InOrderCreate(int depth){
BitNode *bt;
bt=NULL;
if(depth>N)
return NULL;
else{
bt=new BitNode;
bt->lchild=bt->rchild=NULL;
bt->lchild=InOrderCreate(depth+1);
bt->data=data[p++];
bt->rchild=InOrderCreate(depth+1);
}
return bt;
}
void PreOrderOutput(BitTree bt){
if(bt==NULL)
return ;
if(flag){
printf("%d",bt->data);
flag=false;
}
else
printf(" %d",bt->data);
PreOrderOutput(bt->lchild);
PreOrderOutput(bt->rchild);
}
void InOrderOutput(BitTree bt){
if(bt==NULL)
return ;
InOrderOutput(bt->lchild);
if(flag){
printf("%d",bt->data);
flag=false;
}
else
printf(" %d",bt->data);
InOrderOutput(bt->rchild);
}
void PostOrderOutput(BitTree bt){
if(bt==NULL)
return ;
PostOrderOutput(bt->lchild);
PostOrderOutput(bt->rchild);
if(flag){
printf("%d",bt->data);
flag=false;
}
else
printf(" %d",bt->data);
}
int main(){
POW[0]=1;
for(int i=1;i<30;i++)
POW[i]=POW[i-1]+POW[i-1];
BitTree bt;
int M,select;
while(scanf("%d",&N)==1){
for(int i=1;i<POW[N];i++)
data[i]=i;
p=1;
bt=InOrderCreate(1);
scanf("%d",&M);
while(M--){
flag=true;
scanf("%d",&select);
switch(select){
case 1: PreOrderOutput(bt);printf("n"); break;
case 2: InOrderOutput(bt); printf("n"); break;
case 3: PostOrderOutput(bt);printf("n"); break;
}
}
}

//system("pause");
return 0;
}