【TOJ 1224】数据结构练习题――后序遍历二叉树
程序员文章站
2022-04-28 09:21:35
Description 给定一颗二叉树,要求输出二叉树的深度以及后序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。 Input 输入数据分为多组,第一行是测试数据的组数n,下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数,数据为0代表当前结点为空,数据为-1代表二叉树数据输入结 ......
Description
给定一颗二叉树,要求输出二叉树的深度以及后序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。
Input
输入数据分为多组,第一行是测试数据的组数n,下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数,数据为0代表当前结点为空,数据为-1代表二叉树数据输入结束,-1不作处理。二叉树的构造按照层次顺序(即第1层1个整数,第2层2个,第3层4个,第4层有8个......,如果某个结点不存在以0代替)。
Output
输出每棵二叉树的深度以及后序遍历二叉树得到的序列。
Sample input
2
1 -1
1 2 0 3 4 -1
Sample output
1 1
3 3 4 2 1
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int a[1005],k; //k是二叉树元素总数 int post(int n) //n是从1开始的参数,表示遍历到的第n个元素 { if(n>k)return 0; if(a[2*n]!=0) //避免无效遍历导致的内存使用过大 post(2*n); //先从左遍历 if(a[2*n+1]!=0) post(2*n+1); //再从右遍历 if(a[n]) cout<<" "<<a[n]; } int deep(int n) { int m; if(n>k||a[n]==0)return 0; int left=deep(2*n); int right=deep(2*n+1); m=max(left,right)+1; return m; } int main() { int t,n; cin>>t; while(t--) { k=0; while(cin>>n) { if(n==-1)break; a[++k]=n; } cout<<deep(1); //深度从1开始递归 post(1); //中序遍历也从1开始递归 cout<<endl; memset(a,0,sizeof a); } return 0; }
推荐阅读
-
【TOJ 1222】数据结构练习题――先序遍历二叉树
-
【TOJ 1224】数据结构练习题――后序遍历二叉树
-
常见数据结构算法--二叉树的后序遍历序列
-
JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】
-
Java 数据结构中二叉树前中后序遍历非递归的具体实现详解
-
数据结构与算法1:二叉树(binary_tree)的前、中、后序(深度优先)和广度优先遍历及python代码实现
-
Python数据结构之树和二叉树(先序遍历、中序遍历和后序遍历)
-
【TOJ 1224】数据结构练习题――后序遍历二叉树
-
【TOJ 1222】数据结构练习题――先序遍历二叉树
-
常见数据结构算法--二叉树的后序遍历序列