原文链接:https://www.dreamwings.cn/ytu2346/2606.html
2346: 中序遍历二叉树
时间限制: 1 Sec 内存限制: 128 MB
提交: 12 解决: 3
题目描述
给定一颗二叉树,要求输出二叉树的深度以及中序遍历二叉树得到的序列。本题假设二叉树的结点数不超过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 <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) { Print(T->lchild); printf(T->data?" %d":"",T->data); 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; }