YTU 2344: 先序遍历二叉树

YTU 2344: 先序遍历二叉树

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

输出

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

样例输入

21 -11 2 0 3 4 -1

样例输出

1 13 1 2 3 4

思想：根据数据层序建立一棵二叉树，然后对其进行先序遍历即可~

代码：

​

#include #include #include #include #include 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。