2344: 先序遍历二叉树

题目描述

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

输入

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

输出

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

样例输入

2
1 -1
1 2 0 3 4 -1

样例输出

1 1
3 1 2 3 4

参考代码

#include <stdio.h>
#include <stdlib.h>
typedef struct node 
{
    int data;
    struct node *lc, *rc;
}
bnode;
bnode *CreateTree();
bnode *que[100];
bnode *CreateTree() 
{
    int data;
    int front=1, rear=0;
    bnode *root, *s;
    root = NULL;
    scanf("%d", &data);
    while(data != -1) 
    {
        s=NULL;
        if(data != 0) 
        {
            s = (bnode *)malloc(sizeof(bnode));
            s->data = data;
            s->lc = NULL;
            s->rc = NULL;
        }
        rear++;
        que[rear] = s;
        if( rear == 1 ) 
        {
            root = s;
        } else 
        {
            if( s&&que[front] ) 
            {
                if(rear%2 == 0) 
                {
                    que[front]->lc = s;
                } else 
                {
                    que[front]->rc = s;
                }
            }
            if( rear %2 == 1 ) 
            {
                front++;
            }
        }
        scanf("%d", &data);
    }
    return root;
}
void pre( bnode *p ) 
{
    if( p != NULL ) 
    {
        printf(" %d", p->data);
        pre(p->lc);
        pre(p->rc);
    }
}
int dep( bnode *p ) 
{
    int    lh,rh;
    if( p == NULL ) 
    {
        return 0;
    } else 
    {
        lh = dep(p->lc);
        rh = dep(p->rc);
        if( lh > rh ) 
        {
            return lh+1;
        }
        return rh+1;
    }
}
int main() 
{
    bnode *p;
    int t;
    scanf("%d", &t);
    while( t-- ) 
    {
        p = CreateTree();
        printf("%d", dep(p));
        pre(p);
        printf("n");
    }
    return 0;
}

解析

暂无