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

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