若一棵树采用双亲存储结构t存储,用c++语言设计一个算法求索引为i的结点的层次。
时间: 2024-02-22 12:59:03 浏览: 67
《数据结构》5.3树的存储结构
假设双亲存储结构中,每个结点的数据类型为ElemType,其中包含一个int类型的parent变量,表示该结点的双亲结点在数组中的下标。
算法如下:
```cpp
int GetLevel(ElemType t[], int i) {
int level = 0;
while (t[i].parent != -1) { // 当前结点存在双亲结点
i = t[i].parent; // 将当前结点移动到双亲结点
level++; // 层数加1
}
return level;
}
```
该算法的思路是从给定的结点往上遍历,直到根结点。每经过一个结点,层数加1。当遇到根结点时,层数即为该结点的层次。
其中,-1表示该结点没有双亲结点,即为根结点。
注意:该算法时间复杂度为O(h),其中h为树的高度。若树的高度较大,该算法效率将较低,可以考虑采用其他存储结构或优化算法。
阅读全文