详解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 <stdio.h>
#include <stdlib.h>

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;
}