数据结构练习题---先序遍历二叉树

数据结构练习题---先序遍历二叉树

时间限制(普通/Java):3000MS/10000MS          运行内存限制:65536KByte
总提交:107            测试通过:64

描述

给定一颗二叉树，要求输出二叉树的深度以及先序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。

输入

输入数据分为多组，第一行是测试数据的组数n，下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数，数据为0代表当前结点为空，数据为-1代表二叉树数据输入结束，-1不作处理。二叉树的构造按照层次顺序（即第1层1个整数，第2层2个，第3层4个，第4层有8个......，如果某个结点不存在以0代替），比如输入：

 1 2 0 3 4 -1得到的二叉树如下：

 

  

 

 

 

 

 

输出

输出每棵二叉树的深度以及先序遍历二叉树得到的序列。

样例输入

2
1 -1
1 2 0 3 4 -1

样例输出

1 1
3 1 2 3 4

解题思路：首先对输入的数组进行建树，编号为x的结点的左儿子编号一定为2*x，右儿子编号一定为2*x+1，那么根据这个规律就可以把树建好了，然后递归求深度。。。

代码如下：

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <map>
#include <iostream>
using namespace std;
int s[1011],n;
/*typedef struct node
{
    int k;
    struct node *l,*r;
}node,*tree;*/
typedef struct node* tree;
typedef struct node* tree_lr;
struct node{
    int k;
    tree_lr l,r;
};
void bulid_tree(tree &t,int x)///建树
{
    if(x>n|| s[x]==0){
        t=NULL;
        return ;
    }
    t=new node;
    t->k=s[x];
    bulid_tree(t->l,2*x);
    bulid_tree(t->r,2*x+1);
}
int height_tree(tree t)///计算深度
{
    int l=0,r=0;
    if(t==NULL) return 0;
    l=height_tree(t->l)+1;
    r=height_tree(t->r)+1;
    return l>r ? l : r;
}

void print_tree(tree t)///输出，其中中序和后序，只要改变输出顺序就可以了
{
    if(t){
        printf(" %d",t->k);
        print_tree(t->l);
        print_tree(t->r);
    }
}
int main()
{
    tree t;
    t=NULL;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        n=1;
        while(scanf("%d",&s[n])!=EOF)
            if(s[n]==-1) break;
            else n++;
        n--;
        bulid_tree(t,1);
        printf("%d",height_tree(t));
        print_tree(t);
        printf("\n");
    }
    return 0;
}