当前位置 : 主页 > 编程语言 > java >

YTU 2344: 先序遍历二叉树

来源:互联网 收集:自由互联 发布时间:2022-08-15
2344: 先序遍历二叉树 时间限制:1 Sec 内存限制:128 MB 提交:4 解决:3 题目描述 给定一颗二叉树,要求输出二叉树的深度以及先序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1




2344: 先序遍历二叉树


时间限制: 1 Sec   内存限制: 128 MB

提交: 4  

解决: 3


题目描述


给定一颗二叉树,要求输出二叉树的深度以及先序遍历二叉树得到的序列。本题假设二叉树的结点数不超过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 <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
typedef struct Node //定义二叉树
{
int data;
Node* lchild;
Node* rchild;
} TBNode;
int depin;
void Init(TBNode *T) //建立二叉树
{
TBNode *a[105];
TBNode *p=T;
int real=0;
while(cin>>p->data&&p->data!=-1) //层序输入数据
{
a[++real]=p; //当前节点入队
if(real/2!=0) //如果不是根节点,为当前节点父节点添加指针
{
if(real%2)a[real/2]->rchild=p; //如果不能整除二说明是它父节点的右孩子
else a[real/2]->lchild=p; //否则为父节点左孩子
}
p->lchild=NULL; //当前节点孩子指针域设置为NULL
p->rchild=NULL;
p=(TBNode*)malloc(sizeof(TBNode));
}
depin=(int)ceil(log2(real+1)); //二叉树深度为所有节点个数加一 log2(real+1)向上取整
}
void Print(TBNode *T) //先序输出二叉树
{
if(T!=NULL)
{
printf(T->data?" %d":"",T->data);
Print(T->lchild);
Print(T->rchild);
}
}
int main()
{
int N;
cin>>N;
TBNode *Tree; //根节点
Tree=(TBNode*)malloc(sizeof(TBNode));
while(N--)
{
Init(Tree); //建立二叉树
printf("%d",depin); //输出深度
Print(Tree); //输出二叉树
printf("\n");
}
return 0;
}




【本文来源:韩国服务器 http://www.558idc.com/kt.html欢迎留下您的宝贵建议】
上一篇:YTU 3025: 创建二叉树
下一篇:没有了
网友评论