已知后序遍历和中序遍历求层序遍历(树的遍历)
程序员文章站
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
上一篇: UC小游戏开发经验
下一篇: Xib实现 Login 页面