双亲结点
孩子结点
有相同双亲的结点:兄弟结点
一个结点的子结点的个数,称为该结点的度
树中结点的最大度数称为树的度
树的高度(深度)是树中结点的最大层数
同一双亲结点的两个孩子结点之间不存在路径
树中的结点数 等于 所有结点的度数 + 1
这个1就是根结点
度为m的树中第k层上至多有m^(k-1)个结点,k>=1
度为2的树中第k层上至多有2^(k-1)个结点, k>=1
高度为h的m叉树至多有(m^h – 1) / (m – 1)个结点
高度为h的二叉树至多有2^h – 1个结点
推导公式:S = m^(h-1) + m^(h-2) + … + m + 1
S = m^0 + m^1 + … + m^(h – 1) = (1 – m^h) / (1 – m)
附:等比数列求和公式
具有S个结点的m叉树,最小高度为 logm[S* (m – 1) + 1]
具有S个结点的2叉树,最小高度为log2[2*S + 1]