定义:设T是有向树,如果它有一个结点的入度为0,其余结点的入度均为1,则称T为根树.入度为0的结点称为树根,出度非0的结点称为分支点,出度为0的点称为树叶.
从根结点到结点v的有向路长度称为v的层数.最大层数称为树的高度.
定义:如果T的分支点都至多有m个儿子,称T为m元树.若每个分支点都恰有m个儿子,称为正则m元树.若正则m元树的所有树叶都在同一层,称为完全m元树.
定理1. 正则二元树的分支点数i与树叶数t满足\(i=t-1\).
定理2. 设T是一颗正则二元树,I表示各分支点的层数之和,E表示各树叶的层数之和,则\(E=I+2i\).
定义:在所有含t片树叶,且叶子权重分别为\(w_1\cdotsw_t\)的二元树中,权最小的二元树称为最优二元树.
一个二元前缀码唯一对应一颗有序二元树.