首页 > 代码库 > Codevs 二叉树遍历问题 合集
Codevs 二叉树遍历问题 合集
2010 求后序遍历
时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver
题目描述 Description
输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。
输入描述 Input Description
共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。
输出描述 Output Description
仅一行，表示树的后序遍历序列。
样例输入 Sample Input
abdehicfg
dbheiafcg
样例输出 Sample Output
dhiebfgca
数据范围及提示 Data Size & Hint
输入长度不大于255。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 string n,m; 6 void postorder(int lp,int rp,int li,int ri) 7 { 8 if(lp==rp) { cout<<n[lp];return; } 9 if(lp>rp||li>ri) return ;10 int k=m.find(n[lp]);11 postorder(lp+1,lp+k-li,li,k-1);12 postorder(lp+k-li+1,rp,k+1,ri);13 cout<<n[lp];14 }15 int main()16 {17 cin>>n>>m;18 int len=n.size();19 postorder(0,len-1,0,len-1);20 return 0;21 }
只需要在前序遍历中找出根节点，在中序遍历中划分开左右子树的列表，然后再继续递归即可~~
3143 二叉树的序遍历
时间限制: 1 s 空间限制: 32000 KB 题目等级 : 白银 Silver
题目描述 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<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 int n,x,y; 6 struct node{ 7 int left,right; 8 }tree[256]; 9 void preorder(int k)10 {11 cout<<k<<‘ ‘;12 if(tree[k].left!=0)13 preorder(tree[k].left);14 if(tree[k].right!=0)15 preorder(tree[k].right);16 }17 void inorder(int k)18 {19 if(tree[k].left!=0)20 inorder(tree[k].left);21 cout<<k<<‘ ‘;22 if(tree[k].right!=0)23 inorder(tree[k].right);24 }25 void postorder(int k)26 {27 if(tree[k].left!=0)28 postorder(tree[k].left);29 if(tree[k].right!=0)30 postorder(tree[k].right);31 cout<<k<<‘ ‘;32 }33 int main()34 {35 scanf("%d",&n);36 for(int i=1;i<=n;i++)37 {38 scanf("%d%d",&x,&y);39 tree[i].left=x;tree[i].right=y;40 }41 preorder(1);// 前序遍历 42 cout<<endl;43 inorder(1);44 cout<<endl;45 postorder(1);46 return 0;47 }
Codevs 二叉树遍历问题 合集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。