欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

已知后序遍历和中序遍历求层序遍历(树的遍历)

程序员文章站 2022-05-04 09:22:48
#includeusing namespace std;typedef long long ll;const int maxn = 1e4 + 10;const int inf = 0x3f3f3f3f;const ll INF = 1ll << 62;const double PI = acos(-1);const double eps = 1e-7;const int mod = 998244353;#define speed {i...

L2-006 树的遍历 (25分)
给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式:
输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式:
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。

输入样例:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例:
4 1 6 3 5 7 2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 10;
const int inf = 0x3f3f3f3f;
const ll INF = 1ll << 62;
const double PI = acos(-1);
const double eps = 1e-7;
const int mod = 998244353;
#define speed {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); }

int  in[50], post[50];//中序与后序
struct node//建立节点并初始化
{
	int value;
	node *l, *r;
	node(int value = 0, node *l = NULL, node *r = NULL) :value(value), l(l), r(r) {}
};
void buildtree(int l, int r, int &t, node * &root)
{
	int flag = -1;
	for (int i = l; i <= r; i++)
	{
		if (post[t] == in[i])
		{
			flag = i;
			break;
		}
	}
	if (flag == -1)return;
	root = new node(in[flag]);
	t--;//后序数组从后往前(先序数组从前往后)
	if (flag < r)buildtree(flag + 1, r, t, root->r);//已知后序的话先建立右子树
	if (flag > l)buildtree(l, flag - 1, t, root->l);//已知先序的话先建立左子树
}
vector<int>save[50];//用来存储每个深度的节点的值
void dfs(node *root, int deep)
{
	if (root == NULL)return;
	save[deep].push_back(root->value);
	dfs(root->l, deep + 1);
	dfs(root->r, deep + 1);
}
int cnt = 0;
int res[50];
void  inorder(node *root)//输出中序排列(本题不用)
{
	if (root != NULL)
	{
		inorder(root->l);
		res[cnt++] = root->value;
		inorder(root->r);
	}
}
void Free(node *root)//清除空间
{
	if (root != NULL)
	{
		Free(root->l);
		Free(root->r);
		delete root;
	}
	else return;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &post[i]);
	for (int i = 1; i <= n; i++)scanf("%d", &in[i]);
	node *root;
	int t = n;
	buildtree(1, n, t, root);

	/*inorder(root);
	for (int i = 0; i < cnt; i++)
		printf("%d ", res[i]);*/

	dfs(root, 0);
	int f = 0;
	for (int i = 0; i < 50; i++)
	{
		if (save[i].size() == 0)break;//如果读到的层数中无内容说明读完了
		for (int j = 0; j < save[i].size(); j++)
		{
			if (f == 0) { printf("%d", save[i][j]); f = 1; }
			else printf(" %d", save[i][j]);
		}
	}
	Free(root);
	//system("pause");
	return 0;
}

本文地址:https://blog.csdn.net/m0_49041421/article/details/107400135

相关标签: 二叉树