数据结构问题:设树T采用双亲表示的存储结构，编程，计算该树的高度

Question

数据结构问题:设树T采用双亲表示的存储结构，编程，计算该树的高度

Answer 1

算法思路：
从双亲表示的最后一个下标的元素开始，依次对每个结点计数一直到根跳转的次数，这个最大值就是树的高度追问

可以给出算法代码不

追答

双亲表示的情况参见严慰敏《数据结构》教材

#define MAX_TREE_SIZE 500
typedef struct PTNode
{ // 双亲表示结点
TElemType data;
int parent; // 双亲位置
} PTNode;
typedef struct
{ // 树
PTNode nodes[MAX_TREE_SIZE];
int r, n; // 根的位置与结点数
} PTree;

int Height(PTree *t)
{
int i, j, hmax = 0, h;
for (i = t->n - 1; i >= 0; i --)
{ // 双亲表示中的下标从0 开始
h = 0;
for (j = i; j != -1; j = t->nodes[j].parent)
h ++;
if (h > hmax)
hmax = h;
}
return hmax;
}
其实如果严格按照双亲表示的按树的层次序存放，这个外层循环可以去掉的，因为最后一个元素的高度肯定最大