|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
#pragma region 二叉树模板
|
|
|
|
|
|
//二叉树结点结构
|
|
|
typedef struct TreeNode {
|
|
|
bool data; //结点数据
|
|
|
string num;
|
|
|
struct TreeNode *left; //左孩子
|
|
|
struct TreeNode *right; //右孩子
|
|
|
} *BinaryTree; //定义BinaryTree为指向 struct TreeNode(结构体TreeNode)的指针
|
|
|
|
|
|
|
|
|
//通过字符串数据，按层遍历反向构建完全二叉树
|
|
|
BinaryTree RebuildBinaryTree(string *arr, int n) {
|
|
|
//构建一个指针组成的数组
|
|
|
vector<BinaryTree> trees;
|
|
|
//遍历每一个字符串数组中的字符串，构建指针，然后将指针添加到指针数组中去
|
|
|
for (int i = 0; i < n; i++) {
|
|
|
//实例化指针
|
|
|
BinaryTree tree = new TreeNode();
|
|
|
tree->num = arr[i];
|
|
|
tree->data = false;//指针为->，对象为.
|
|
|
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(BinaryTree T) {
|
|
|
//利用递归前序输出二叉树
|
|
|
if (T) {
|
|
|
cout << T->data << " ";
|
|
|
PreOrderTraverse(T->left);
|
|
|
PreOrderTraverse(T->right);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//中序遍历
|
|
|
void InOrderTraverse(BinaryTree T) {
|
|
|
//利用递归中序输出二叉树
|
|
|
if (T) {
|
|
|
InOrderTraverse(T->left);
|
|
|
cout << T->data << " ";
|
|
|
InOrderTraverse(T->right);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//后序遍历
|
|
|
void PostOrderTraverse(BinaryTree T) {
|
|
|
//利用递归后序输出二叉树
|
|
|
if (T) {
|
|
|
PostOrderTraverse(T->left);
|
|
|
PostOrderTraverse(T->right);
|
|
|
cout << T->data << " ";
|
|
|
}
|
|
|
}
|
|
|
|
|
|
void PreOrderTraverseWithLevel(BinaryTree T, int level, vector<vector<BinaryTree>> &vec) {
|
|
|
if (T) {
|
|
|
if (vec.size() < level + 1) {
|
|
|
vector<BinaryTree> arr;
|
|
|
vec.push_back(arr);
|
|
|
}
|
|
|
vec[level].push_back(T);
|
|
|
PreOrderTraverseWithLevel(T->left, level + 1, vec);
|
|
|
PreOrderTraverseWithLevel(T->right, level + 1, vec);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//层次遍历
|
|
|
void LevelOrderTraverse(BinaryTree T) {
|
|
|
if (T) {
|
|
|
vector<vector<BinaryTree>> vec;
|
|
|
PreOrderTraverseWithLevel(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 二叉树模板
|
|
|
BinaryTree tree;
|
|
|
|
|
|
string doAction(BinaryTree T) {
|
|
|
if (T->left == NULL && T->right == NULL)
|
|
|
return T->num;
|
|
|
if (!T->data) {
|
|
|
//左子树
|
|
|
T->data = true;
|
|
|
return doAction(T->left);
|
|
|
} else {
|
|
|
//右子树
|
|
|
T->data = false;
|
|
|
return doAction(T->right);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//转换整数到字符串
|
|
|
string intToStr(int n) {
|
|
|
char str[256] = {0};
|
|
|
sprintf(str, "%d", n);
|
|
|
return str;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
int n, l;
|
|
|
cin >> n >> l;
|
|
|
int count = pow(2, n) - 1;
|
|
|
string arr[10000];
|
|
|
for (int i = 0; i < count; ++i) {
|
|
|
arr[i] = intToStr(i + 1);
|
|
|
}
|
|
|
//构建完全二叉树（满二叉树）
|
|
|
tree = RebuildBinaryTree(arr, count);
|
|
|
|
|
|
//l次掉落
|
|
|
string nodeNum;
|
|
|
for (int i = 0; i < l; ++i) {
|
|
|
nodeNum = doAction(tree);
|
|
|
}
|
|
|
//输出结果
|
|
|
cout << nodeNum << endl;
|
|
|
return 0;
|
|
|
}
|
