若是凉夜已成梦

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


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

2344: 先序遍历二叉树

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

题目描述

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

解析

暂无

hustoj

发表评论 取消回复

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

*
*


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

若是凉夜已成梦

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

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

友情链接

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