【TOJ 1222】数据结构练习题――先序遍历二叉树
程序员文章站
2022-09-26 17:03:14
Description 给定一颗二叉树,要求输出二叉树的深度以及先序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。 Input 输入数据分为多组,第一行是测试数据的组数n,下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数,数据为0代表当前结点为空,数据为-1代表二叉树数据输入结 ......
Description
给定一颗二叉树,要求输出二叉树的深度以及先序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。
Input
输入数据分为多组,第一行是测试数据的组数n,下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数,数据为0代表当前结点为空,数据为-1代表二叉树数据输入结束,-1不作处理。二叉树的构造按照层次顺序(即第1层1个整数,第2层2个,第3层4个,第4层有8个......,如果某个结点不存在以0代替),比如输入:
1 2 0 3 4 -1得到的二叉树如下:
Output
输出每棵二叉树的深度以及先序遍历二叉树得到的序列。
Sample input
2
1 -1
1 2 0 3 4 -1
Sample output
1 1
3 1 2 3 4
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int a[1001],k; int pre(int n) { if(n>k)return 0;
if(a[n]) cout<<" "<<a[n]; if(a[2*n]!=0) pre(2*n);
if(a[2*n+1]!=0) pre(2*n+1); } int deep(int n) { int m; if(n>k||a[n]==0) return 0; //a[n]=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); pre(1); cout<<endl; memset(a,0,sizeof a); } return 0; }
上一篇: 似懂非懂的Comparable与Comparator
下一篇: 我的Python之旅第三天