详解C/C++中二叉树高度的算法与代码实现
二叉树的高度定义
二叉树的高度被定义为从根节点到任何叶节点的最长路径长度，即从根节点到任何叶节点的最大深度。
让我们考虑下面的二叉树。
由于与最大深度对应的叶子节点是40和50，要找到高度，我们只需找到从根节点到这两个节点中的任何一个的边的数量，即3。
现在我们知道了二叉树的高度代表什么，所以我们将构建一个算法来找到任意二叉树的高度。
用C++编写的二叉树高度的逻辑
现在让我们决定寻找高度的逻辑，并首先编写伪代码。
我们将使用树的递归来找到高度。(请参考维基百科文章了解相关概念)
由于树的高度被定义为从根到叶子的最长路径，我们可以递归计算左子树和右子树的高度。
我们现在可以对子树应用高度的定义。
我们观察到这是左子树和右子树之间的最大值加一。
由于树的高度等于其子树的最大高度加1，我们会一直重复此过程，直到子树变为空，并且其高度为0。
此时，我们的功能将最终终止。
让我们编写一个名为tree_height()的函数来计算树的高度。
// 查找由根节点定义的树的高度
int tree_height(Node* root) {
if (root == NULL)
return 0;
else {
// 查找左、右子树的高度
left_height = tree_height(root->left);
right_height = tree_height(root->right);
// 查找max(子树高度) + 1来获取树的高度
return max(left_height, right_height) + 1;
}
第3行评估终止条件，即当子树大小为0或根节点为空时。
第7行和第8行递归地找出左子树和右子树的高度。
最终，第11行返回两者中较大的值，即返回树的高度。
在C/C++中的实现
以下是一个完整的程序，展示了如何构建二叉树，并展示了在tree_height()函数中查找树高的逻辑。
#include
#include
typedef struct Node Node;
// 在此定义树节点
struct Node {
int value;
// 指向左右子节点的指针
Node* left, *right;
};
Node* init_tree(int data) {
// 创建树并返回根节点
Node* root = (Node*) malloc (sizeof(Node));
root->left = root->right = NULL;
root->value = data;
return root;
}
Node* create_node(int data) {
// 创建一个新节点
Node* node = (Node*) malloc (sizeof(Node));
node->value = data;
node->left = node->right = NULL;
return node;
}
void free_tree(Node* root) {
// 释放树中每个节点对应的内存
Node* temp = root;
if (!temp)
return;
free_tree(temp->left);
free_tree(temp->right);
if (!temp->left && !temp->right) {
free(temp);
return;
}
}
int tree_height(Node* root) {
// 获取树的高度
if (!root)
return 0;
else {
// 找出两个子树的高度并使用较大的那个
int left_height = tree_height(root->left);
int right_height = tree_height(root->right);
if (left_height >= right_height)
return left_height + 1;
else
return right_height + 1;
}
}
int main() {
// 演示如何查找二叉树高度的程序
// 创建值为10的根节点
Node* root = init_tree(10);
// 向树插入节点
root->left = create_node(20);
root->right = create_node(30);
root->left->left = create_node(40);
root->left->right = create_node(50);
// 查找树的高度
int height = tree_height(root);
printf("二叉树的高度: %d\n", height);
// 释放树的内存！
free_tree(root);
return 0;
}