数据结构_树_1_基本概念


双亲结点

孩子结点

有相同双亲的结点:兄弟结点

一个结点的子结点的个数,称为该结点的

树中结点的最大度数称为树的度

 

树的高度(深度)是树中结点的最大层数

同一双亲结点的两个孩子结点之间不存在路径

 

树中的结点数 等于 所有结点的度数 + 1

这个1就是根结点

 

度为m的树中第k层上至多有m^(k-1)个结点,k>=1

度为2的树中第k层上至多有2^(k-1)个结点, k>=1


高度为hm叉树至多有(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]