先/中/后序遍历二叉树

我会带着你远行 2022-05-30 10:28 136阅读 0赞

给定一颗二叉树，要求输出二叉树的深度以及先序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。

输入

输入数据分为多组，第一行是测试数据的组数n，下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数，数据为0代表当前结点为空，数据为-1代表二叉树数据输入结束，-1不作处理。二叉树的构造按照层次顺序（即第1层1个整数，第2层2个，第3层4个，第4层有8个......，如果某个结点不存在以0代替），比如输入：

1 2 0 3 4 -1得到的二叉树如下：

![1222.gif][]

输出

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

样例输入

2  
1 -1

1 2 0 3 4 -1

样例输出

1 1

3 1 2 3 4

这里以先序遍历为例。中/后序的遍历只要挪一下输出的位置就行了。

#include<stdio.h>
    #include<math.h>
    int a[100],i;//1222
    void first(int n)
    {	
    	//输出非空结点 
    	printf(" %d",a[n]);//先序 
    	if(a[2*n+1]!=0)
    		first(2*n+1);	
    	//printf(" %d",a[n]);中序
    	if(a[2*n+2]!=0)
    		first(2*n+2);
    	//printf(" %d",a[n]);后序
    }
    int main()
    {
    	int t,b,k;
    	scanf("%d",&t);
    	while(t--)
    	{
    		i=0;
    		while(1)
    		{
    			scanf("%d",&b);
    			if(b==-1)break;
    			a[i++]=b;
    		}
    		k=int(log(i)/log(2)+1.1);
    		printf("%d",k);//深度
    		first(0);
    		printf("\n");
    	}
    }

[1222.gif]: http://acm.tzc.edu.cn/acmhome/judge/images/1222.gif

发表评论取消回复

表情：

评论列表（有 0 条评论，136人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树的遍历——先序遍历、中序遍历、后序遍历

遍历二叉树（本文的二叉树均使用指针方式构建）先序遍历操作定义：若二叉树为空，则空操作；否则： 1. 访问根节点； 2. 先序遍历左子树； 3

淡淡的烟草味﹌/ 2022年12月01日 15:44/ 0 赞/ 223 阅读

相关二叉树的创建，先序遍历，中序遍历，后序遍历

![Center][] ![Center 1][] include<stdio.h> include<stdlib.h>

桃扇骨/ 2022年08月19日 02:11/ 0 赞/ 164 阅读

相关二叉树创建、先序遍历、中序遍历、后序遍历、树深度

一、概念：二叉树遍历：按指定的某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。根节点N，按照先遍历左子树L再

旧城等待，/ 2022年07月16日 03:24/ 0 赞/ 244 阅读

相关二叉树先序遍历中序遍历建立二叉树然后后序遍历

题目描述二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左

男娘i/ 2022年06月01日 07:24/ 0 赞/ 219 阅读

相关先/中/后序遍历二叉树

给定一颗二叉树，要求输出二叉树的深度以及先序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。输入输入数据分为多组，第一行是测试数据的组数n，下面的n行分别代

我会带着你远行/ 2022年05月30日 10:28/ 0 赞/ 137 阅读

相关先序创建二叉树及先序、中序、后序遍历

先序二叉树 //先序建立二叉树 void createBiTree(BiTree &T){ int cnt; scanf("%d",&cn

短命女/ 2022年05月27日 09:09/ 0 赞/ 145 阅读

相关中序遍历和先序遍历/后序遍历构建二叉树

1、问题给定二叉树的2个遍历序列（如先序+中序，先序+后序，中序+后序等），是否能够根据这2个遍历序列唯一确定二叉树？ 2

- 日理万妓/ 2022年03月19日 04:22/ 0 赞/ 259 阅读

相关中序遍历和先序遍历/后序遍历构建二叉树

1、问题给定二叉树的2个遍历序列（如先序+中序，先序+后序，中序+后序等），是否能够根据这2个遍历序列唯一确定二叉树？ 2、理论分析数据结构的基础知识中重要的一点

布满荆棘的人生/ 2022年02月25日 07:44/ 0 赞/ 289 阅读

相关二叉树(先序遍历，中序遍历，后序遍历)

二叉树定义每个节点的子节点数(度)不能大于2 先序遍历定义：从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。

悠悠/ 2021年10月01日 09:18/ 0 赞/ 427 阅读

相关树之二叉树遍历先序，中序，后序

一、介绍 ![这里写图片描述][20160905190552651] 二、遍历理解 ![这里写图片描述][20160905190704230] 三、先序算法

青旅半醒/ 2021年09月11日 01:46/ 0 赞/ 538 阅读