题目：哈夫曼编码求完全二叉树叶结点编号
有一棵完全二叉树，包含n 个节点。将其叶子节点自左向右从0开始编号。
现有一个小球，从根节点出发向下移动，其移动轨迹可以用0-1串表示，其中0表示从当前节点移动到其左孩子，1表示从当前节点移动到其右孩子。
当给出小球的移动轨迹，请计算小球到达叶子节点的编号。
如图2所示，该完全二叉树包含11个节点。当小球移动轨迹为001时，到达叶子节点的编号为1；
移动轨迹为10时，到达叶子节点的编号为4；移动轨迹为01时，小球未到达叶子节点；
移动轨迹为101时，小球超出二叉树范围。
输入样例1：
11（节点个数）
001（移动轨迹）
输出样例1：
1（到达叶子节点的编号）
输入样例2：
11（节点个数）
01（移动轨迹）
输出样例2：
路径太短
输入样例3：
11（节点个数）
101（移动轨迹）
输出样例3：
路径太长
代码示例👇
//author:Mitchell_Donovan
//date:4.27
#include<iostream>
using namespace std;
void routeFind(int size, string route);
int main() {
int size;
cout << "请输入节点个数：";
cin >> size;
string route;
cout << "请输入路径：";
cin >> route;
routeFind(size, route);
}
void routeFind(int size, string route) {
int routeLength = 0;
for (int i = 0; i < route.length(); i++) {
if (route[i] == '0') {
routeLength = 2 * routeLength + 1;
}
else if (route[i] == '1') {
routeLength = 2 * routeLength + 2;
}
}
if (routeLength >= size) {
cout << "路径太长";
return;
}
else if (routeLength <= size / 2 - 1) {
cout << "路径太短";
return;
}
//x记录叶子位置
int x = 0;
//降到最左最深树叶
while (2 * x + 1 < size) {
x = 2 * x + 1;
}
//i记录叶子编号
int i = 0;
for (; i + x < size; i++) {
if (routeLength == i + x) {
cout << i;
return;
}
}
//补全i
while (i + x < size) {
i++;
}
for (int j = size / 2; j < x; j++) {
if (routeLength == j) {
cout << i << endl;
return;
}
else {
i++;
}
}
}
