二叉树的序遍历x（内含结构体与非结构体版x）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

3143 codevs 二叉树的序遍历

题目描述 Description

求一棵二叉树的前序遍历，中序遍历和后序遍历

输入描述 Input Description

第一行一个整数n，表示这棵树的节点个数。

接下来n行每行2个整数L和R。第i行的两个整数Li和Ri代表编号为i的节点的左儿子编号和右儿子编号。

输出描述 Output Description

输出一共三行，分别为前序遍历，中序遍历和后序遍历。编号之间用空格隔开。

样例输入 Sample Input

2 3

4 5

0 0

样例输出 Sample Output

1 2 4 5 3

4 2 5 1 3

4 5 2 3 1

数据范围及提示 Data Size & Hint

n <= 16

分类标签 Tags 点此展开

递归搜索

非结构体版x

#include<iostream> using namespace std; int tree[][]= {}; void preorder(int node, int j) { //先序遍历
if(tree[node][j]==) return; cout<<tree[node][j]<<" ";
preorder(tree[node][j], );
preorder(tree[node][j], );
} void inorder(int node, int j) { //中序遍历
if(tree[node][j]==) return; inorder(tree[node][j], );
cout<<tree[node][j]<<" ";
inorder(tree[node][j], );
} void postorder(int node, int j) { //后序遍历
if(tree[node][j]==) return; postorder(tree[node][j], );
postorder(tree[node][j], ); cout<<tree[node][j]<<" ";
} int main() {
int n;//n<=16
cin>>n;
int i, j;
tree[][]=tree[][]=; for (i = ; i <= n; ++i)
for(j=; j<; j++)
cin>>tree[i][j]; preorder(, );
cout<<endl;
inorder(, );
cout<<endl;
postorder(, );
cout<<endl;
return ;
}

结构体版x

#include<iostream>
#include<cstdio>
#include<cstring> using namespace std; struct node {
int l,r;
} t[]; void qian(int root) {
if(!root)return;
printf("%d ",root);
qian(t[root].l);
qian(t[root].r);
} void zhong(int root) {
if(!root)return;
zhong(t[root].l);
printf("%d ",root);
zhong(t[root].r);
}
void hou(int root) {
if(!root)return;
hou(t[root].l);
hou(t[root].r);
printf("%d ",root);
} int main() {
int n,x,y;
scanf("%d",&n);
for(int i=; i<=n; i++) {
scanf("%d%d",&x,&y);
t[i].l=x;
t[i].r=y;
}
qian();
cout<<endl;
zhong();
cout<<endl;
hou();
cout<<endl;
return ;
}