若一棵树采用双亲存储结构t存储,用c++语言设计一个完成的算法,能求索引为i的结点的层次。
时间: 2024-02-22 21:59:08 浏览: 65
算法如下:
```cpp
#include <iostream>
using namespace std;
const int MAXSIZE = 100; // 树的最大结点数
typedef struct {
int data; // 结点数据
int parent; // 双亲结点下标
} ElemType, Tree[MAXSIZE];
int GetLevel(Tree t, int i) {
int level = 0;
while (t[i].parent != -1) { // 当前结点存在双亲结点
i = t[i].parent; // 将当前结点移动到双亲结点
level++; // 层数加1
}
return level;
}
int main() {
Tree t = {
{1, -1}, {2, 0}, {3, 0}, {4, 1}, {5, 1},
{6, 2}, {7, 2}, {8, 3}, {9, 3}, {10, 4}
};
int i = 9;
int level = GetLevel(t, i);
cout << "结点" << i << "的层次为:" << level << endl;
return 0;
}
```
该算法首先定义了一个结构体ElemType,用来表示树的每个结点。然后定义了一个Tree数组,用来存储整棵树,其中Tree的元素类型为ElemType。
GetLevel函数的实现与前面给出的一样,通过循环遍历双亲结点,求出给定结点的层次。在主函数中,定义了一棵树,并求出了给定结点的层次,最后输出结果。
需要注意的是,该算法时间复杂度为O(h),其中h为树的高度。若树的高度较大,该算法效率将较低,可以考虑采用其他存储结构或优化算法。
阅读全文