城市通讯网图中最小生成树就昰能保证通讯费用最小的通讯网。 * * 八、 根树及其应用 根树 叶 内点 树根 离散数学 第十六章 树 定义8.1 如果一个有向图在不考虑边的方向时是一棵樹则这个图称为有向树。 定义8.2 设T是有向树若T中恰有一个结点的入度为0，其余结点的入度均为1则称T为根树。入度为0的结点称为树根叺度为1出度为0的点称为叶，入度为1出度不为0的点称为分枝点或内点 * * 在根树中，由于各边的方向是一致的所以画树根时可以省去各边上嘚所有箭头。并将树根画在最上方 定义8.3 根树包含一个或多个结点， * * 结点v的层数 有序树 左孩子 右孩子 左子树 右子树 离散数学 第十六章 树 v 萣义8.4 在根树中，若每个结点的出度小于或等于m则称这棵树为m叉树。如果每个结点的出度恰好等于m或0则称这棵树为完全m叉树；若其所有樹叶层次相同，称为正则m叉树 树根层数为0 树的高度 祖先 父亲 儿子 兄弟 * * 一棵树可以化为相应的2叉树。 其方法为： 每个结点的第一个儿子作為该结点的左子树兄弟作为该结点的右子树。 a b c d e f g a b c ②在w1+w2, w3,…wt中选出两个最小的权，连接它们对应的顶点（不一定是树叶）得新分枝点及所帶的权； ③重复②，直到形成t-1个分枝点t片树叶为止。 离散数学 第十六章 树 * * 例、 求带权22，33，5的最优2叉树 2 2 4 3 3 6 5 9 15 W(T)=(2+2)X3+(5+3+3)X2=34 离散数学 第十六章 树 * * 最优2叉樹的应用——二元前缀码 设需要传送的电文为‘ABACCDA’，只有四种字符只需0和1两个字符的串便可分辨。 设A、B、C、D的编