codevs 3143 二叉树的序遍历
题目描述 Description
求一棵二叉树的前序遍历，中序遍历和后序遍历
输入描述 Input Description
第一行一个整数n，表示这棵树的节点个数。
接下来n行每行2个整数L和R。第i行的两个整数Li和Ri代表编号为i的节点的左儿子编号和右儿子编号。
输出描述 Output Description
输出一共三行，分别为前序遍历，中序遍历和后序遍历。编号之间用空格隔开。
样例输入 Sample Input
5
2 3
4 5
0 0
0 0
0 0
样例输出 Sample Output
1 2 4 5 3
4 2 5 1 3
4 5 2 3 1
数据范围及提示 Data Size & Hint
n <= 16
1 #include <stdio.h> 2 int n,a[100][2]={0};//节点数n，顺序存储的二叉树 3 void PreOrder(int b) /*先序遍历的递归算法*/ 4 { 5 printf("%d ",b); /*访问根结点*/ 6 if(a[b][0]!=0) PreOrder(a[b][0]); 7 if(a[b][1]!=0) PreOrder(a[b][1]); 8 } 9 void InOrder(int b) /*中序遍历的递归算法*/ 10 { 11 if(a[b][0]!=0) 12 InOrder(a[b][0]); 13 printf("%d ",b); /*访问根结点*/ 14 if(a[b][1]!=0) 15 InOrder(a[b][1]); 16 } 17 void PostOrder(int b) /*后序遍历的递归算法*/ 18 { 19 if(a[b][0]!=0) PostOrder(a[b][0]); 20 if(a[b][1]!=0) PostOrder(a[b][1]); 21 printf("%d ",b); /*访问根结点*/ 22 } 23 int main() 24 { 25 int i,x,y; 26 freopen("data.in","r",stdin); 27 28 scanf("%d",&n); 29 for(i=1;i<=n;i++) 30 { 31 scanf("%d%d",&x,&y); 32 a[i][0]=x;//节点i的左孩子 33 a[i][1]=y;//节点i的右孩子 34 } 35 PreOrder(1); 36 printf("\n"); 37 38 InOrder(1); 39 printf("\n"); 40 41 PostOrder(1); 42 printf("\n"); 43 44 return 0; 45 }
何泓历的代码：
1 #include <stdio.h> 2 int a[17][2]={0},b[9]={0,1,2,1,0,2,1,2,0}; 3 void F(int i,int x) 4 { 5 if(!i) return;//如果节点为空则返回 6 int j; 7 for(j=x;j<x+3;j++) 8 { 9 switch(b[j]){ 10 case 0:printf("%d ",i);break; 11 case 1:F(a[i][0],x);break; 12 case 2:F(a[i][1],x);break; 13 } 14 } 15 } 16 int main() 17 { 18 int n,i; 19 scanf("%d",&n); 20 for(i=1;i<=n;i++) scanf("%d%d",&a[i][0],&a[i][1]); 21 for(i=0;i<7;i+=3) 22 { 23 F(1,i); 24 printf("\n"); 25 } 26 return 0; 27 }
非递归遍历：
1 #include<iostream> 2 #include<stdio.h> 3 #include<stack> 4 using namespace std; 5 6 int n,a[100][2]={0};//节点数n，顺序存储的二叉树 7 8 void PreOrder(int b) /*先序遍历的非递归算法*/ 9 { 10 stack<int> St; 11 int p; 12 St.push(b); //根结点入栈 13 while(!St.empty())//栈不为空时循环 14 { 15 p=St.top(); St.pop(); //退栈并访问该结点 16 printf("%d ",p); 17 if(a[p][1]!=0) //右孩子结点入栈 18 { 19 St.push(a[p][1]); 20 } 21 if (a[p][0]!=0)//左孩子结点入栈 22 { 23 St.push(a[p][0]); 24 } 25 } 26 } 27 28 void InOrder(int b) /*中序遍历的非递归算法*/ 29 { 30 stack<int> St; 31 int p; 32 p=b; 33 while(!St.empty() || p!=0) 34 { 35 while(p!=0)//扫描p的所有左结点并进栈 36 { 37 St.push(p); 38 p=a[p][0];//p指向p节点的左孩子节点 39 } 40 if(!St.empty()) 41 { 42 p=St.top(); St.pop(); //出栈p结点 43 printf("%d ",p); //访问之 44 p=a[p][1]; //扫描p的右孩子结点 45 } 46 } 47 } 48 49 void PostOrder(int b) /*后序遍历的非递归算法*/ 50 { 51 stack<int> St; 52 int p; 53 int flag; 54 do 55 { 56 while(b!=0) //将b节点的所有左结点进栈 57 { 58 St.push(b); 59 b=a[b][0];//b指向b节点的左孩子 60 } 61 p=0; //p指向栈顶结点的前一个已访问的结点 62 flag=1; //设置b的访问标记为已访问过 63 while(!St.empty() && flag==1) 64 { 65 b=St.top(); //取出当前的栈顶元素 66 if(a[b][1]==p) 67 { 68 printf("%d ",b); //访问b结点 69 St.pop();p=b; //p指向则被访问的结点 70 } 71 else 72 { 73 b=a[b][1]; //b指向右孩子结点 74 flag=0; //设置未被访问的标记 75 } 76 } 77 }while(!St.empty()); 78 } 79 80 int main(int argc, char *argv[]) 81 { 82 int i,x,y; 83 freopen("data.in","r",stdin); 84 85 scanf("%d",&n); 86 for(i=1;i<=n;i++) 87 { 88 scanf("%d%d",&x,&y); 89 a[i][0]=x;//节点i的左孩子 90 a[i][1]=y;//节点i的右孩子 91 } 92 PreOrder(1); 93 printf("\n"); 94 95 InOrder(1); 96 printf("\n"); 97 98 PostOrder(1); 99 printf("\n");/**/ 100 return 0; 101 }
何泓历的代码：
1 #include <stdio.h> 2 #include <string.h> 3 int n,i,j,b[9]={0,1,2,1,0,2,1,2,0};//先序，中序，后序 4 int zhan[101],top,flag,a[3][17]={0};// a0i左孩子,a1i右孩子,a2i表示是否访问过 5 int F(int x)//b[x]~b[x+2]表示访问的顺序 6 { 7 flag=0; 8 switch(x){ 9 case 0:if(!a[2][zhan[top]])//访问根节点 10 {printf("%d ",zhan[top]);a[2][zhan[top]]=1;}break; 11 case 1:if(!a[2][a[0][zhan[top]]]&&a[0][zhan[top]])//访问左孩子 12 {zhan[++top]=a[0][zhan[top-1]];flag=1;}break; 13 case 2:if(!a[2][a[1][zhan[top]]]&&a[1][zhan[top]])//访问右孩子 14 {zhan[++top]=a[1][zhan[top-1]];flag=1;}break; 15 } 16 return flag; 17 } 18 int main() 19 { 20 scanf("%d",&n); 21 for(i=1;i<=n;i++) scanf("%d%d",&a[0][i],&a[1][i]); 22 for(i=0;i<7;i+=3) 23 { 24 zhan[1]=1;top=1;memset(a[2],0,sizeof(a[2]));//初始化 25 while(top) 26 { 27 if(F(b[i])) continue;//如果访问左孩子或右孩子则进入 28 if(F(b[i+1])) continue; 29 if(F(b[i+2])) continue; 30 top--; 31 } 32 printf("\n"); 33 } 34 return 0; 35 }
