108 lines
2.4 KiB
C++
108 lines
2.4 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 1e6 + 10;
|
||
|
||
//树的结构体+存储数组
|
||
//此处：为二叉树的标准创建、遍历模板，可用于其它试题！
|
||
struct Node {
|
||
int id; // 当前结点ID
|
||
int left; // 左结点ID
|
||
int right; // 右结点ID
|
||
char value; //当前结点的value值
|
||
} t[N];
|
||
|
||
//前序遍历
|
||
void pre_order(Node node) {
|
||
//利用递归前序输出二叉树
|
||
if (node.id) {
|
||
cout << node.value << " ";
|
||
pre_order(t[node.left]);
|
||
pre_order(t[node.right]);
|
||
}
|
||
}
|
||
|
||
//中序遍历
|
||
void in_order(Node node) {
|
||
//利用递归前序输出二叉树
|
||
if (node.id) {
|
||
in_order(t[node.left]);
|
||
cout << node.value << " ";
|
||
in_order(t[node.right]);
|
||
}
|
||
}
|
||
|
||
|
||
//后序遍历
|
||
void post_order(Node node) {
|
||
//利用递归前序输出二叉树
|
||
if (node.id) {
|
||
post_order(t[node.left]);
|
||
post_order(t[node.right]);
|
||
cout << node.value << " ";
|
||
}
|
||
}
|
||
|
||
//层序遍历
|
||
void level_order(Node node) {
|
||
queue<Node> q;
|
||
//放入第一个
|
||
q.push(node);
|
||
while (!q.empty()) {
|
||
Node n1 = q.front();
|
||
q.pop();
|
||
cout << n1.value << " ";
|
||
if (n1.left > 0) q.push(t[n1.left]);
|
||
if (n1.right > 0) q.push(t[n1.right]);
|
||
}
|
||
}
|
||
|
||
int n, m;
|
||
|
||
/**
|
||
测试数据：
|
||
1 7
|
||
1 2 3
|
||
2 4 5
|
||
3 0 7
|
||
4 0 0
|
||
5 6 0
|
||
6 0 0
|
||
7 0 0
|
||
*/
|
||
int main() {
|
||
cin >> n >> m;
|
||
//n组数据
|
||
for (int i = 1; i <= n; i++) {
|
||
//清空结构体数组,这个玩意好暴力啊
|
||
memset(&t, 0, sizeof(t));
|
||
|
||
//创建树
|
||
for (int j = 1; j <= m; j++) {
|
||
cin >> t[j].value >> t[j].left >> t[j].right;
|
||
t[j].id = j;
|
||
}
|
||
cout << endl;
|
||
cout << "树" << i << ":" << endl;
|
||
//前序
|
||
cout << "前序：";
|
||
pre_order(t[1]);
|
||
cout << endl;
|
||
//中序
|
||
cout << "中序：";
|
||
in_order(t[1]);
|
||
cout << endl;
|
||
//后序
|
||
cout << "后序：";
|
||
post_order(t[1]);
|
||
cout << endl;
|
||
//层序
|
||
cout << "层序：";
|
||
level_order(t[1]);
|
||
cout << endl;
|
||
cout << "====================================================" << endl;
|
||
cout << endl;
|
||
}
|
||
return 0;
|
||
}
|
||
//深度就是树的层数，本题为4
|