欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【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得到的二叉树如下:

【TOJ 1222】数据结构练习题――先序遍历二叉树

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; }