C/C++ 中二叉树的高度是多少？

二叉树的高度被定义为从根节点到任何叶节点的最长路径长度，即从根节点到任何叶节点的最大深度。

让我们考虑下面的二叉树。

由于与最大深度对应的叶子节点是40和50，要找到高度，我们只需找到从根节点到这两个节点中的任何一个的边的数量，即3。

现在我们知道了二叉树的高度代表什么，所以我们将构建一个算法来找到任意二叉树的高度。

用C++编写的二叉树高度的逻辑

现在让我们决定寻找高度的逻辑，并首先编写伪代码。

我们将使用树的递归来找到高度。(请参考维基百科文章了解相关概念)

由于树的高度被定义为从根到叶子的最长路径，我们可以递归计算左子树和右子树的高度。

我们现在可以对子树应用高度的定义。

我们观察到这是左子树和右子树之间的最大值加一。

由于树的高度等于其子树的最大高度加1，我们会一直重复此过程，直到子树变为空，并且其高度为0。

此时，我们的功能将最终终止。

让我们编写一个名为tree_height()的函数来计算树的高度。

// Find height of a tree, defined by the root node
int tree_height(Node* root) {
    if (root == NULL) 
        return 0;
    else {
        // Find the height of left, right subtrees
        left_height = tree_height(root->left);
        right_height = tree_height(root->right);
         
        // Find max(subtree_height) + 1 to get the height of the tree
        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;

// Define the Tree Node here
struct Node {
    int value;
    // Pointers to the left and right children
    Node* left, *right;
};


Node* init_tree(int data) {
    // Creates the tree and returns the
    // root node
    Node* root = (Node*) malloc (sizeof(Node));
    root->left = root->right = NULL;
    root->value = data;
    return root;
}

Node* create_node(int data) {
    // Creates a new node
    Node* node = (Node*) malloc (sizeof(Node));
    node->value = data;
    node->left = node->right = NULL;
    return node;
}

void free_tree(Node* root) {
    // Deallocates memory corresponding
    // to every node in the tree.
    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) {
    // Get the height of the tree
    if (!root)
        return 0;
    else {
        // Find the height of both subtrees
        // and use the larger one
        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() {
    // Program to demonstrate finding the height of a Binary Tree

    // Create the root node having a value of 10
    Node* root = init_tree(10);
    
    // Insert nodes onto the tree
    root->left = create_node(20);
    root->right = create_node(30);
    root->left->left = create_node(40);
    root->left->right = create_node(50);

    // Find the height of the tree
    int height = tree_height(root);
    printf("Height of the Binary Tree: %d\n", height);

    // Free the tree!
    free_tree(root);
    return 0;
}