数据结构问题:设树T采用双亲表示的存储结构,编程,计算该树的高度
答案:1 悬赏:20 手机版
解决时间 2021-11-15 11:07
- 提问者网友:听门外雪花风
- 2021-11-15 00:37
数据结构问题:设树T采用双亲表示的存储结构,编程,计算该树的高度
最佳答案
- 五星知识达人网友:像个废品
- 2021-11-15 01:21
算法思路:
从双亲表示的最后一个下标的元素开始,依次对每个结点计数一直到根跳转的次数,这个最大值就是树的高度追问可以给出算法代码不追答双亲表示的情况参见严慰敏《数据结构》教材
#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;
}
其实如果严格按照双亲表示的按树的层次序存放,这个外层循环可以去掉的,因为最后一个元素的高度肯定最大
从双亲表示的最后一个下标的元素开始,依次对每个结点计数一直到根跳转的次数,这个最大值就是树的高度追问可以给出算法代码不追答双亲表示的情况参见严慰敏《数据结构》教材
#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;
}
其实如果严格按照双亲表示的按树的层次序存放,这个外层循环可以去掉的,因为最后一个元素的高度肯定最大
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯