c++编写一个程序,实现二叉树高度的求取。利用二叉树的性质及二叉树前序遍历的思想,计算二叉树的高度。
时间: 2023-11-14 17:09:30 浏览: 51
以下是C++代码实现:
```c++
#include <iostream>
using namespace std;
// 定义二叉树的结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 计算二叉树的高度
int getHeight(TreeNode* root) {
if (root == NULL) {
return 0;
}
int left_height = getHeight(root->left);
int right_height = getHeight(root->right);
return max(left_height, right_height) + 1;
}
int main() {
// 构建一个二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 计算二叉树的高度并输出
int height = getHeight(root);
cout << "The height of the binary tree is: " << height << endl;
return 0;
}
```
该程序首先定义了二叉树的结构体,包含节点的值、左子树和右子树。接着,定义了一个递归函数 `getHeight`,该函数用于计算二叉树的高度。
在函数中,如果当前节点为空,则返回0。否则,分别计算左子树和右子树的高度,取其中较大值并加1,即为当前节点所在子树的高度。
最后,在 `main` 函数中构建了一个二叉树,并调用 `getHeight` 函数计算二叉树的高度并输出。
阅读全文