3143 二叉树的序遍历

在这解道问题前先学习一下什么是二叉树的序遍历。

二叉树的序遍历分为前序遍历，中序遍历和后序遍历。

 

前序遍历：
前序遍历（DLR）是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右，即其遍历先从根节点开始，再依次遍历左右子节点。

中序遍历：

中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游，可记做左根右，即其遍历从左子节点开始，再依次遍历根节点和右子节点。

后序遍历：

后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根，即其遍历从左子节点开始，再依次遍历右子节点和根节点。

e.g.

上图的前序遍历结果为：

ABDECF

中序遍历结果为：

DBEAFC

后序遍历结果为：

DEBFCA

 

题目描述 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

根据不同的遍历方法设计三种递归

 

AC代码：

1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 5 int x[100000],y[100000]; 6 7 void q(int n){ 8 if(n){ 9 cout<<n<<" "; 10 q(x[n]); 11 q(y[n]); 12 } 13 } 14 15 void z(int n){ 16 if(n){ 17 z(x[n]); 18 cout<<n<<" "; 19 z(y[n]); 20 } 21 } 22 23 void h(int n){ 24 if(n){ 25 h(x[n]); 26 h(y[n]); 27 cout<<n<<" "; 28 } 29 } 30 31 int main(){ 32 int n; 33 cin>>n; 34 memset(x,0,sizeof(x)); 35 memset(y,0,sizeof(y)); 36 for(int i=1;i<=n;i++){ 37 cin>>x[i]>>y[i]; 38 } 39 q(1); 40 cout<<endl; 41 z(1); 42 cout<<endl; 43 h(1); 44 cout<<endl; 45 return 0; 46 }

 

转载于:https://www.cnblogs.com/Kiven5197/p/5665581.html

总结

以上是生活随笔为你收集整理的3143 二叉树的序遍历的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。