2346: 中序遍历二叉树

题目描述

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

输入

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

输出

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

样例输入

2
1 -1
1 2 0 3 4 -1

样例输出

1 1
3 3 2 4 1

参考代码

#include<stdio.h>
#include<stdlib.h>
#define maxsize 20
typedef struct node 
{
    int ltag,rtag;
    int data;
    struct node *lch,*rch;
}
btnode;
btnode *Q[maxsize];
int flag;
btnode *creat() 
{
    int c;
    int front,rear;
    btnode *T,*S;
    T=NULL;
    front=1;
    rear=0;
    scanf("%d",&c);
    while(c!=-1) 
    {
        S=NULL;
        if(c!=0) 
        {
            S=(btnode *)malloc(sizeof(btnode));
            S->data=c;
            S->lch=NULL;
            S->rch=NULL;
            S->rtag=0;
            S->ltag=0;
        }
        rear++;
        Q[rear]=S;
        if(rear==1) T=S; else 
        {
            if(S!=NULL && Q[front]!=NULL)
                            if(rear%2==0) Q[front]->lch=S; else Q[front]->rch=S;
            if(rear%2==1) front++;
        }
        scanf("%d",&c);
    }
    return T;
}
void pre(btnode *T) 
{
    if(T) 
    {
        if(T->ltag!=1) pre(T->lch);
        if(flag) 
        {
            printf(" ");
        }
        flag=1;
        printf("%d",T->data);
        if(T->rtag!=1) pre(T->rch);
    }
}
int depth(btnode *bt) 
{
    int m,n;
    if(bt==NULL)
            return 0;
    m=depth(bt->lch);
    n=depth(bt->rch);
    if(m>n)
            return m+1; else
            return n+1;
}
int main() 
{
    int n;
    scanf("%d",&n);
    while(n--) 
    {
        flag=0;
        btnode *bt;
        bt=creat();
        printf("%d ",depth(bt));
        pre(bt);
        printf("n");
    }
    return 0;
}

解析

暂无