西安电子科技大学：《离散数学》课程教学课件（题解）第七章 图论 7-7-2 树

西安电子科技大学离散数学软件学院第四篇图论第6章图论第27-28课时6.1图的基本概念-第29课时6.2路径与回路→第30课时6.3图的矩阵表示第31-32课时6.4欧拉图与汉密尔顿图6.5平面图第33课时V第34课时6.6图的着色大第36课时6.7树(2)大之6.8图的应用第37-38课时

西安电子科技大学 离散数学 软件学院 第四篇 图论 6.1 图的基本概念 第6章 图论 6.4 欧拉图与汉密尔顿图 6.2 路径与回路 6.5 平面图 第29课时 第33课时 第30课时 6.3 图的矩阵表示 第34课时 6.6 图的着色 第31－32课时 第36课时 6.7 树（2） 第27－28课时 第37 －38课时 6.8 图的应用

西安电子科技大学根树$6.7.4软件学院若一个有向图T的底图是一棵无向树，则称T为有向树有向树?a

西安电子科技大学 根树 软件学院 有向树 §6.7.4

西安电子科技大学根树$6.7.4软件学院家一棵有向树T，若恰有一个结点的入度为0，其余结点的根树入度均为1，则称T为根树或外向树。入度为0的结点称为树根，出度为0的结点称为树叶，出度不为0的结点称为分支点或内点

西安电子科技大学 §6.7.4 根树 软件学院 根树

西安电子科技大学根树$6.7.4软件学院从根r到结点v的路径长度称为结点v的层次。结点的层次在根树T=中，若从结点a到b可达，则称a是b的祖先（ancestor），b是a的后裔(descendant）。若EE，则称a是b的父亲（father），b是a的儿子（son）。如果两个结点a和b有相同的父亲，则称a与b是兄弟(siblings)o

西安电子科技大学 §6.7.4 根树 软件学院 结点的层次 在根树T=中，若从结点a到b可达，则称 a是b的祖先（ancestor），b是a的后裔 （descendant）。若∈E，则称a是b的 父亲（father），b是a的儿子（son）。如果两 个结点a和b有相同的父亲，则称a与b是兄弟 （siblings）

西安电子科技大学根树$6.7.4软件学院在根树中，如果规定了同层结点的次序，这样的根有序树树称为有序树。m叉树每个结点的出度均小于等于m的根树。完全m叉树每个结点的出度均等于m或等于0的根树

西安电子科技大学 根树 软件学院 有序树 §6.7.4 m叉树 完全m叉树

西安电子科技大学$6.7.4 根树软件学院家定理」设有完全m叉树T，其树叶数为t，分枝结点数为i，则有（m-1)i=t-1。证明由题设知，树T有i+t个结点，则T中有i+t-1条边。根据有向图的握手定理知，所有结点的出度和等于边数，则有mxi=i+t-1即(m-1)i=t-1证毕

西安电子科技大学 §6.7.4 根树 软件学院 证明 由题设知，树T 有i+t个结点，则T中有i+t-1条 边。根据有向图的握手定理知，所有结点的出度和等 于边数，则有 m×i=i+t-1 即 (m-1)i=t-1 证毕

西安电子科技大学摩根树$6.7.4软件学险茶-【例题】网球锦标赛共有7名选手闯入最后的总决赛。比赛采用单淘汰制，问需要多少场比赛才能决出冠军？+~35纳达尔纳达休依特

西安电子科技大学 §6.7.4 根树 软件学院

西安电子科技大学$6.7.4 根树软件学院茶家【例题】设有一台计算机，它的指令系统包含有一条加法指令，该指令最多能够一次计算3个浮点数的和。如果要计算20个浮点数的和，最少要运行该指令多少次？解若把这20个浮点数均看作是完全三叉树的树叶，该完全三叉树的分支结点看作是执行一次3个浮点数的加法指令，设分支结点数为i，则有(3-1)i≥20-1所以有i≥19/2，即最少要运行该指令10次

西安电子科技大学 §6.7.4 根树 软件学院 【例题】 设有一台计算机，它的指令系统包含有一条加 法指令，该指令最多能够一次计算3个浮点数的和。如果 要计算20个浮点数的和，最少要运行该指令多少次？ 解 若把这20个浮点数均看作是完全三叉树的树叶，该 完全三叉树的分支结点看作是执行一次3个浮点数的加法 指令，设分支结点数为i，则有 (3-1)i≥20-1 所以有i≥19/2，即最少要运行该指令10次

西安电子科技大学$6.7.5最优树软件学院家下面我们来讨论最优树，它起源于计算机科学、生产管理等领域。举一个简单的例子，地铁自动售票机使用内置的逻辑程序自动分辨用户投入的1角、伍角或1元这三种硬币（假设分辨三种硬币的时间同），如果以上三种硬币出现的概率分别为0.1、0.3、0.6。问应如何设计程序中的逻辑分支算法，使得系统在运行过程中使用的平均时间最短？

西安电子科技大学 §6.7.5 最优树 软件学院 下面我们来讨论最优树，它起源于计算机科学、生产管理 等领域。举一个简单的例子，地铁自动售票机使用内置的 逻辑程序自动分辨用户投入的1角、伍角或1元这三种硬币 （假设分辨三种硬币的时间相同），如果以上三种硬币出 现的概率分别为0.1、0.3、0.6。问应如何设计程序中的 逻辑分支算法，使得系统在运行过程中使用的平均时间最 短？

西安电子科技大学$6.7.5最优树软件学院家家给定一组权值Wi，W2，.，Wt，不妨设WisW2≤...Wt带权2叉树设有一棵二叉树，共有t片树叶，分别带权Wi，W2，..Wt则该二叉树称为带权二叉树。在带权二叉树中，若带权为Wi的树叶，根到该树叶的路径最优2叉树长度为L(w)，称W(T)=ZW,L(W）称为该带权二叉树的权。1-1在所有带权Wi,W2.W,的二叉树中，W(T)最小的那棵树称为最优二叉树

西安电子科技大学 §6.7.5 最优树 软件学院 带权2叉树 最优2叉树