文章
11
粉丝
216
获赞
4
访问
102.7k
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
/*
思路:
构建满三叉树,满三叉树结点i的祖先结点为 fa = (i + 1)/3;
lchild = fa * 3 - 1 ; michild = fa * 3; rchild = fa * 3 + 1;
通过回溯来寻找最短路径,回溯一次,路径长度加一;
并在此过程记录各自的回溯路径;拼接即可得最终路径
*/
struct node
{
int data;
int pr;
} sk[100];
int triTree[1005]; //满三叉树
map<int, int> inde; //建立结点的data到满三叉树的index的映射
int p1[100], p2[100]; //用于存储以两个端结点为起点的回溯路径
int len1, len2;
bool cmp(node a, node b)
{
return a.pr < b.pr;
}
//找最短路径
void spl(int n, int m) //n,m为端点结点在满三叉树中的下标索引
{
p1[0] = triTree[n];
p2[0] = triTree[m];
len1 = 1; len2 = 1;
while (n != m)
{
if (n > m)
{
n = (n + 1) / 3;
p1[len1++] = triTree[n];
}
else
{
m = (m + 1) / 3;
p2[len2++] = triTree[m];
}
}
len1-- ; //交汇点重复
}
//输出路径
v...
登录后发布评论
暂无评论,来抢沙发