以二叉链表作为二叉树的存储结构,计算二叉树的高度和最大的宽度(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。 [题目分析]求最大宽度可采用层次遍历的方法,记下各层结点数,每层遍历完毕,若结点数大于原先最大宽度,则修改最大宽度。
时间: 2024-03-14 16:46:05 浏览: 41
好的,我来为您解答这道题。
首先,二叉树的高度可以通过递归来计算。我们可以写一个递归函数 getHeight,该函数接受一个二叉树结点作为参数,返回以该结点为根节点的子树的高度。具体实现如下:
```
int getHeight(BiTree root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return max(leftHeight, rightHeight) + 1;
}
```
接下来,我们要计算二叉树的最大宽度。我们可以采用层次遍历的方法,记下各层结点数,每层遍历完毕,若结点数大于原先最大宽度,则修改最大宽度。具体实现如下:
```
int getMaxWidth(BiTree root) {
if (root == NULL) {
return 0;
}
queue<BiTree> q; // 定义一个队列用于层次遍历
q.push(root); // 根节点入队
int maxWidth = 1; // 初始化最大宽度为1
while (!q.empty()) {
int size = q.size(); // 当前层的结点数
for (int i = 0; i < size; i++) {
BiTree node = q.front();
q.pop();
if (node->left != NULL) {
q.push(node->left);
}
if (node->right != NULL) {
q.push(node->right);
}
}
// 更新最大宽度
if (q.size() > maxWidth) {
maxWidth = q.size();
}
}
return maxWidth;
}
```
综上,我们可以通过以上两个函数来计算二叉树的高度和最大宽度。