若一棵树采用孩子链存储结构t存储,设计一个算法求其高度
时间: 2024-05-04 11:18:57 浏览: 12
可以使用递归的思想来实现求一棵树的高度。
具体实现思路如下:
1. 如果树为空,高度为0
2. 如果树非空,对于树中每一个孩子结点,递归求出其高度,并取其中的最大值,再加上1即为整棵树的高度。
以下是求树高的C++代码实现:
```c++
// 树的孩子链存储结构的定义
#define MAX_TREE_SIZE 100
typedef struct CTNode
{
int child; // 孩子结点在数组中的位置下标
struct CTNode *next; // 指向下一个兄弟结点
} *ChildPtr;
typedef struct
{
int data;
ChildPtr firstchild; // 孩子链表头指针
} CTBox;
typedef struct
{
CTBox nodes[MAX_TREE_SIZE]; // 结点数组
int n, r; // 结点数和根的位置
} CTree;
// 递归求树的高度
int TreeHeight(CTree t, int p)
{
int h = 0;
ChildPtr child = t.nodes[p].firstchild;
while (child != NULL)
{
int ch_height = TreeHeight(t, child->child);
if (ch_height > h)
h = ch_height;
child = child->next;
}
return h + 1;
}
// 测试代码
int main()
{
CTree t;
// 假设树已经建好,根结点为t.r
int height = TreeHeight(t, t.r);
cout << "树的高度为:" << height << endl;
return 0;
}
```