树的内部节点：非叶子节点
树的外部节点：叶子节点

如何计算一个树的深度和高度

计算树的深度

假设p是树t中的一个节点，那么p的深度就是p的祖先节点的数量，对此我们可以用递归的方法来实现，如果p是跟节点，返回0，否则返回1+其父节点的深度

    def depth(p):
        '''return the depth of node p'''
        if is_root(p):
            return 0
        else:
            return 1+depth(parent(p))

计算树的高度

一个节点p的高度定义如下：

• 如果p是叶子节点，那么高度为0
• 否则p的高度等与p的叶子节点中的最大高度加1

    def height(p):
        '''return the height of node p'''
        if is_leaf(p):
            return 0
        else:
            return 1+max(height(c) for c in children(p))

二叉树：

特点：

• 每个节点最多两个孩子
• 两个孩子分别为左孩子和右孩子
• 在顺序上，左孩子优于右孩子
• 在一颗非空完全二叉树中，有ne个外部节点和ni个内部节点，则ne = ni + 1
• 设T为非空二叉树，n，ne，ni和h分别表示T的节点数，外部节点数，内部节点数和高度，则有
  • h+1 <= n <= 2^(h+1)-1
  • 1 <= ne <= 2^(h)
  • h <= ni <= 2^(h)-1
  • log(n+1)-1 <= h <= n-1
    若T是完全二叉树
  • 2h+1 <= n <= 2^(h+1)-1
  • h+1 <= ne <= 2^(h)
  • h <= ni <= 2^(h)-1
  • log(n+1)-1 <= h <= （n-1)/2
    若每个节点都有零个或者两个孩子节点，则称为完全二叉树