若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

2346: 中序遍历二叉树

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,265

题目描述

给定一颗二叉树,要求输出二叉树的深度以及中序遍历二叉树得到的序列。本题假设二叉树的结点数不超过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;
}

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Dreams孤独患者 Skip 原站点
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist