【TOJ 1224】數據結構練習題――後序遍歷二叉樹

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