文章

4

粉丝

0

获赞

4

访问

67419

头像
在树的结构中找任意两个结点的最短路径-------采用满多叉树的方式存储和处理
经验总结
发布于2021年2月25日 19:08
阅读数 8188

题目ID:1654

#include<iostream>
#include<cstring>

using namespace std;

/*
思路:把二叉树当成满二叉树来存储;
      较大位置的结点往上回溯,直到二者相遇,每一次回溯,路径长度加一。
*/

int Bitree[1005];
int inde[1005];        //i号结点在满二叉树中的下标索引
void spl(int p1, int p2)
{
    int len = 0;
    while (p1 != p2)
    {
        len++;
        if (p1 > p2)  p1 /= 2;
        else  p2 /= 2;
    }

    cout << len << endl;
}
int main()
{
    int t, n, m;

    while (cin >> t)
    {
        if (t = 0) break;
        t--;
        cin >> n >> m;

        memset(Bitree, 0, sizeof(Bitree)); //初始化满二叉树
        Bitree[1] = 1;
        inde[1] = 1;
        for (int i = 1; i <= n; i++)   //建立满二叉树
        {
            int x, y;
            cin >> x >> y;
            if (x > 0) inde[x] = inde[i] * 2;
            if (y > 0) inde[y] = inde[i] * 2 + 1;
            Bitree[ inde[x] ] = x;
            Bitree[ inde[y] ] = y;
        }

        for (int i = 0; i < m; i++)
        {
            int x, y;
            cin >> x >> y;
            spl(inde[x] , inde[y]);
        }
    }

  return 0;
}

 



登录后发布评论

暂无评论,来抢沙发