完全二叉树的层序遍历[天梯赛]
文章目录
- 题目描述
- 思路
题目描述
输入样例
8
91 71 2 34 10 15 55 18
输出样例
18 34 55 71 2 10 15 91
思路
完全二叉树最后一层可以不满，但上面的每一层的节点数都是满的
后序遍历的顺序为"左右根"，我们可以用数组模拟完全二叉树，从节点1开始寻找，寻找每一个树的根对应的下标，进行输出，最后输出，即为层序遍历的结果
#include <bits/stdc++.h>
using namespace std;
const int N = 40;
int tree[N];
int n;
void dfs(int x)
{if(x > n) return;dfs(2 * x);dfs(2 * x + 1);cin >> tree[x];
}
int main()
{cin >> n;dfs(1);for(int i = 1; i <= n; i ++){if(i != n) cout << tree[i] << " ";else cout << tree[i] << endl;}return 0;
}
欢迎大家批评指正！！！