137 lines
3.8 KiB
C++
137 lines
3.8 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
// 【算法】二叉树的前序、中序、后序、层序遍历和还原。
|
||
// https://www.cnblogs.com/yanyojun/archive/2018/08/28/9488452.html
|
||
|
||
#pragma region 二叉树模板
|
||
|
||
//二叉树结点结构
|
||
typedef struct Node {
|
||
string data; //结点数据
|
||
struct Node *left; //左孩子
|
||
struct Node *right; //右孩子
|
||
} *Tree; //定义了一个指针，这个指针是一个TreeNode的指针
|
||
|
||
|
||
//通过字符串数据，按层遍历反向构建完全二叉树
|
||
Tree RebuildCompleteBinaryTree(string *arr, int n) {
|
||
//构建一个指针组成的数组
|
||
vector<Tree> trees;
|
||
//遍历每一个字符串数组中的字符串，构建指针，然后将指针添加到指针数组中去
|
||
for (int i = 0; i < n; i++) {
|
||
//实例化指针
|
||
Tree tree = new Node();
|
||
tree->data = arr[i];//指针为->，对象为.
|
||
tree->left = NULL;
|
||
tree->right = NULL;
|
||
trees.push_back(tree);
|
||
}
|
||
//从下往上遍历
|
||
/*
|
||
0
|
||
1 2
|
||
3 4 5 6
|
||
*/
|
||
for (int i = trees.size() - 1; i > 0; i--) {
|
||
//奇数
|
||
if (i % 2 != 0) {
|
||
trees[(i - 1) / 2]->left = trees[i]; //好巧妙的 (i-1)/2，这个除法是整数除法，还带取整的，牛！
|
||
} else//偶数
|
||
{
|
||
trees[(i - 1) / 2]->right = trees[i]; //好巧妙的 (i-1)/2，这个除法是整数除法，还带取整的，牛！
|
||
}
|
||
}
|
||
return trees[0];//返回根节点
|
||
}
|
||
|
||
|
||
//前序遍历
|
||
void PreOrderTraverse(Tree T) {
|
||
//利用递归前序输出二叉树
|
||
if (T) {
|
||
cout << T->data << " ";
|
||
PreOrderTraverse(T->left);
|
||
PreOrderTraverse(T->right);
|
||
}
|
||
}
|
||
|
||
//中序遍历
|
||
void InOrderTraverse(Tree T) {
|
||
//利用递归中序输出二叉树
|
||
if (T) {
|
||
InOrderTraverse(T->left);
|
||
cout << T->data << " ";
|
||
InOrderTraverse(T->right);
|
||
}
|
||
}
|
||
|
||
//后序遍历
|
||
void PostOrderTraverse(Tree T) {
|
||
//利用递归后序输出二叉树
|
||
if (T) {
|
||
PostOrderTraverse(T->left);
|
||
PostOrderTraverse(T->right);
|
||
cout << T->data << " ";
|
||
}
|
||
}
|
||
|
||
// level : 用来控制是第几层的，默认为第0层，每一层增加1
|
||
// 容器 : vector<vector<Tree>> &vec
|
||
// 层序遍历(递归的核心函数)
|
||
void PreLevelOrderTraverse(Tree T, int level, vector<vector<Tree>> &vec) {
|
||
//如果当前节点不是空
|
||
if (T) {
|
||
//如果当前行数不够，换句话说，就是又该新增加一层的时候，声明一个数组，追加上去。
|
||
if (vec.size() < level + 1) {
|
||
vector<Tree> arr;
|
||
vec.push_back(arr);
|
||
}
|
||
|
||
//将当前的指针保存到数组中
|
||
vec[level].push_back(T);
|
||
|
||
//递归左子树
|
||
PreLevelOrderTraverse(T->left, level + 1, vec);
|
||
|
||
//递归右子树
|
||
PreLevelOrderTraverse(T->right, level + 1, vec);
|
||
}
|
||
}
|
||
|
||
//层次遍历
|
||
void LevelOrderTraverse(Tree T) {
|
||
if (T) {
|
||
vector<vector<Tree>> vec;
|
||
|
||
//通过层序递归遍历进行构建
|
||
PreLevelOrderTraverse(T, 0, vec);
|
||
|
||
//输出构建结果
|
||
for (int i = 0; i < vec.size(); i++) {
|
||
for (int j = 0; j < vec[i].size(); j++) {
|
||
cout << vec[i][j]->data << " ";
|
||
}
|
||
cout << endl;
|
||
}
|
||
}
|
||
}
|
||
|
||
#pragma endregion 二叉树模板
|
||
|
||
// https://www.cnblogs.com/libin123/p/10420158.html
|
||
int main() {
|
||
string s;
|
||
cin >> s;
|
||
|
||
string arr[1000];
|
||
for (int i = 0; i < s.size(); ++i) {
|
||
arr[i] = s[i];
|
||
}
|
||
|
||
Tree root = RebuildCompleteBinaryTree(arr, s.size());
|
||
PostOrderTraverse(root);
|
||
return 0;
|
||
}
|