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

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[],k;
int pre(int n)
{
    if(n>k)return ;<br />if(a[n])
    cout<<" "<<a[n];
    
    if(a[*n]!=)
    pre(*n);<br />if(a[*n+]!=)
    pre(*n+);
} 
int deep(int n)
{
    int m;
    if(n>k||a[n]==) return ;   //a[n]=0时就跳出，不用递归浪费空间
    int left=deep(*n);
    int right=deep(*n+);
    m=max(left,right)+;
    return m;
}
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        k=;
        while(cin>>n)
        {
            if(n==-)break;
            a[++k]=n;
        }
        cout<<deep();
        pre();
        cout<<endl;
        memset(a,,sizeof a);
    }
    return ;
}