二叉树的高度定义为任何叶节点距根节点的最大深度。
也就是说，它是从根节点到任何叶节点的最长路径的长度。

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

由于对应于最大深度的叶节点为40和50，因此要找到高度，我们只需找到从根节点到这两个节点之一的边数，即3。

现在我们知道二叉树的高度表示什么，现在我们将构造一个算法来查找任何二叉树的高度。

在C++中查找二叉树的高度的逻辑

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

我们将在树上使用递归来找到高度。
(有关概念，请参阅Wikipedia文章)

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

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

我们观察到它是左右子树之间的最大值，然后加一。

由于树的高度是子树的最大高度+ 1，因此我们一直这样做，直到子树变为" NULL"，并且其高度为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;
}

当子树的大小为0或者根节点为NULL时，第3行评估终止条件。

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