课后题 数据结构 ds.05.01.03 解答题
第 117 题

已知一棵度为4的树中,度为0,1,2,3的结点数分别为14,4,3,2,求该树的结点总数n 和度为4的结点数,并给出推导过程。

[tag_link]

参考答案

度为 4 的结点数 n4=2,总结点数 n=25。

推导过程

按结点分类,n=14+4+3+2+n4=23+n4。按度数和加 1,n=1+1×4+2×3+3×2+4n4=17+4n4。联立得 23+n4=17+4n4,所以 n4=2,代回得 n=25。

评分要点

    1. 列出结点分类等式
    1. 列出度数和加 1 等式
    1. 联立求得 n4=2、n=25