数学离散血2026年9月22日星期二
2026年9月22日星期二
曲主要内容1.完全二叉树2.Huffman算法2026/9/22计算机学院2
2026/9/22 计算机学院 2 主要内容 1.完全二叉树 2.Huffman算法
中内容回顾设T是一棵有向树，如果恰有一个结定义11.4点的入度为0，，其余所有结点的入度均为1，则称为根树或外向树入度为0的结点称为树根；出度为0的结点称为树叶；入度为1，出度大于0的结点称为内点；又将内点同树根统称为分支点如果恰有一个结点的出度为0,其余所有(如上例结点的出度均为1，则称为内向树。中的(d))2026/9/22计算机学院
2026/9/22 计算机学院 3 内容回顾 定义11.4 设T是一棵有向树，如果恰有一个结 点的入度为0，其余所有结点的入度均为1，则 称为根树或外向树。 入度为0的结点称为树根；出度为0的结点 称为树叶；入度为1，出度大于0的结点称为内 点；又将内点同树根统称为分支点。 如果恰有一个结点的出度为0，其余所有 结点的出度均为1，则称为内向树。（如上例 中的(d))
m叉树心定义11.5在根树T中，若每个分支点的出度至多为m，贝则称T为m叉树若每个分支点的出度都等于m，则称T为完全的m叉树若T的全部叶结点位于同一层次，则称T为正则m叉树二叉树的每个结点v至多有两棵子树，分别称为v的左子树和右子树2026/9/22计算机学院
2026/9/22 计算机学院 4 m叉树 定义11.5 在根树T中，若每个分支点的出度至 多为m，则称T为m叉树； 若每个分支点的出度都等于m，则称T为完 全的m叉树； 若T的全部叶结点位于同一层次，则称T为 正则m叉树； 二叉树的每个结点v至多有两棵子树，分 别称为v的左子树和右子树
心定理11.5若T是完全m叉树，其树叶数为t，分支点数为i，则下式成立：(m-1) ×i=t-1证明由假设知，该树有i+t个结点。由定理11.1知，该树的边数为i+t-1。（握手定因为所有结点的出度之和等于边数理），所以根据完全的m叉树的定义知，有mi=i+t-1即(m-1) ×i=t-1计算机学院2026/9/225
2026/9/22 计算机学院 5 定理11.5 若T是完全m叉树，其树叶数为t，分支点数为 i，则下式成立： （m-1）×i＝t-1 证明 由假设知，该树有i+t个结点。 ▪ 由定理11.1知，该树的边数为i+t-1。 ▪ 因为所有结点的出度之和等于边数（握手定 理），所以根据完全的m叉树的定义知，有 m×i＝i+t-1 ▪ 即 （m-1）×i＝t-1