沿每个节点v到根r的唯一通路上节点数目，称作v 的深度（depth），记作depth(v)。
依据深度排序，可对所有节点做分层归类。特别地，约定根节点的深度 depth(root) = 1，
故属于第1层。
树T中所有节点深度的最大值称作该树的高度（height），记作height(T)。空树的高度为0。
下面这棵二叉树的高度为3。
我们可以递归的计算出左子树的高度和右子树的高度，然后取二者的最大值加1最为这棵二叉树的高度。
Algorithm:
height(T)
1. 如果树为空，则返回0
2. 否则
(a) 通过递归地调用height(T.left)求出左子树的高度
(b) 通过递归的调用height(T.right)求出右子树的高度
(c) 利用如下公式求出二叉树的高度：
height(T) = max(height(T.left), height(T.right)) + 1
(d) 返回height(T)下图诠释了递归求解过程:
height('1') = max(height('2'), height('3')) + 1
= 2 + 1
/ \
/ \
/ \
/ \
/ \
height('2') = 1 height('3') = 1
= max(height('4'), height('5')) + 1
= 1 + 1 = 2
/ \
/ \
/ \
/ \
/ \
height('4') = 1 height('5') = 1
#include
#include
/* * 二叉树节点包含数据域，指向左子树的指针，指向右子树的指针 */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* * 计算二叉树的高度 */
int height(struct node* node) {
if (node==NULL)
return 0;
else
{
// 计算左子树的高度和右子树的高度
int lHeight = height(node->left); int rHeight = height(node->right); // 返回二者较大者加1
if (lHeight > rHeight)
return(lHeight+1);
else return(rHeight+1);
}
}
/* * 辅助函数 * 使用给定的数据生成二叉树节点，节点的左子树和右子树均为空 */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Height of tree is %d", height(root));
getchar();
return 0;
}