4523: 【作】【基础】二叉树遍历(2203)

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

小明学完了树的基本知识，想做二叉树遍历的程序设计练习。

根据二叉树的深度从数据文件中读入 lns="http://www.w3.org/1998/Math/MathML">n 个整数生成顺序存储的二叉树，做各种遍历的输出。小明发现输出的数据中有不少重复的，为此他先将重复的数据过滤掉，然后再生成二叉树的结构。

现在要求你从数据文件中读取若干个整数，生成一个满二叉树，然后输出一个二叉树遍历的序列。

输入

输入包含 lns="http://www.w3.org/1998/Math/MathML">2 行；

第一行是两个整数 lns="http://www.w3.org/1998/Math/MathML">h 和 lns="http://www.w3.org/1998/Math/MathML">p ，lns="http://www.w3.org/1998/Math/MathML">h 是二叉树的深度， lns="http://www.w3.org/1998/Math/MathML">h≤8 。lns="http://www.w3.org/1998/Math/MathML">p=1时先序输出，lns="http://www.w3.org/1998/Math/MathML">p=2 时中序输出，lns="http://www.w3.org/1998/Math/MathML">p=3 时后序输出。

第二行若干个整数（数字小于等于 lns="http://www.w3.org/1998/Math/MathML">1000 ），读入数据前，先要计算二叉树的结点个数 lns="http://www.w3.org/1998/Math/MathML">n ，然后在数据中顺序读取 lns="http://www.w3.org/1998/Math/MathML">n 个不重复的整数。

例如深度为 lns="http://www.w3.org/1998/Math/MathML">3 的二叉树结点有 lns="http://www.w3.org/1998/Math/MathML">7 个。

输出

输出文只有一行，是二叉树遍历的序列。

样例输入 复制 

3 2
277 248 494 88 277 371 387 88 494 216 227

样例输出 复制 

88 248 371 277 387 494 216

提示

【样例解释】

样例数据构建的二叉树为：

  

#include<bits/stdc++.h>
using namespace std;
int h,p,a[1000],n;

void dfs1(int x) {
	cout<<a[x]<<" ";
	if (2*x<=n&&a[2*x]!=0) dfs1(2*x);
	if (2*x+1<=n&&a[2*x+1]!=0) dfs1(2*x+1);
}

void dfs2(int x) {
	if (2*x<=n&&a[2*x]!=0) dfs2(2*x);
	cout<<a[x]<<" ";
	if (2*x+1<=n&&a[2*x+1]!=0) dfs2(2*x+1);
}

void dfs3(int x) {
	if (2*x<=n&&a[2*x]!=0) dfs3(2*x);
	if (2*x+1<=n&&a[2*x+1]!=0) dfs3(2*x+1);
	cout<<a[x]<<" ";
}

int main(){
    cin>>n>>p;
    n=int(pow(2,n))-1;
    cin>>a[1];
    int cnt=1;
    int t;
    while (cin>>t){
    	bool flag=false;
    	for (int j=1;j<=cnt;j++) {
    		if (a[j]==t) {
    			flag=true;
    			break;
			}
		}
		if (!flag) a[++cnt]=t;
	}
	if (p==1) dfs1(1);
	else if (p==2) dfs2(1);
	else if (p==3) dfs3(1);
	return 0;
}

来源/分类

提交提交记录统计露一手!