最后更新: 2025-01-22 09:54 查看: 105 次纠错评论(0) 课件开VIP

子树与有序树

定义 $1 0 . 1 4$（子树）设 $u$ 是有根树 $T$ 的任意一顶点，以 $u$ 为根，$u$ 及其所有子孙所组成的顶点集 $V^{\prime}, u$ 到这些子孙的有向路上所有弧组成的弧集记为 $E^{\prime}$ ，称 $T$ 的子图 $T^{\prime}\left(V^{\prime}, E^{\prime}\right)$ 为以 $u$ 为根的子树。

上面讨论有根树时，没有考虑同一分枝点连出的弧的次序。但在计算机科学中的许多具体问题（如编码理论和程序设计语言等）一定要考虑这种弧的次序。为此，我们来引进有序树的概念。

定义 10.15 （有序树）有根树的每个分枝点连出的弧（或者有根树的每一个顶点）从左到右用正整数 $1,2, \cdots, i, \cdots$ 标上标号，称该有根树为有序树。

在确定树或画树的方式中，这些标号如果清楚的话，那么标号可以省略。
定义10．16（ $m$ 分树，正则 $m$ 分树）在树 $T$ 中若每一顶点的儿子个数小于或等于 $m$ ，则称 $T$ 为 $m$ 分树。在树 $T$ 中若每一顶点的儿子个数等于 $m$ 或者等于 0 ，称 $T$ 为正则 $m$ 分树。

一类重要的 $m$ 分树是二分树和正则二分树。对于二分树，一个分枝点的左右两个儿子为根的子树分别称左子树和右子树。

例 10.2 算术表达式可以用二分树表示。算术表达式 $((b+(c+d)) a) \div((e f)-(g+h)(i j))$ 如图 10.5 所示。所有运算对象都处于树叶的位置，所有运算符处于分枝点的位置。如果将分枝点连出的弧的次序改变了，那么所得到的二分树对应的算术表达式也就改变了。

定理 10.10 在正则二分树中，树叶数为 $t$ ，分枝点数为 $i$ ，则 $i=t-1$ 。
 ![图片](/uploads/2025-01/5f6091.jpg)
 
 证明：因为分枝点儿子的总数为 $2 i$ 等于树的顶点数减 1 ，即 $2 i=i+t-1$ ，所以 $i=t-1$ 。
同理可证，在正则 $m$ 分树中，树叶数为 $t$ ，分枝数为 $i$ ，则 $t=(m-1) i+1$ 。
正则二分树的路长度在计算机程序中有重要的应用，它关系到计算机的执行时间。
定理10．11 在正则二分树 $T$ 中，$I$ 表示所有分枝点路长度之总和，$E$ 表示所有树叶的路长度之总和，则 $E=I+2 i$ ，其中 $i$ 为分枝点数。

证明：采用归纳法证明，以分枝点数 $i$ 为归纳变量。
当 $i=1$ 时，$E=2, I=0$ ，所以 $E=I+2 i$ 。假设 $i=k-1$ 时结论成立。当 $i=k$ 时，删去一个分枝点 $v$ 连出的边及其儿子，$v$ 的路长度为 $l$ ，并且它的两个儿子是树叶，那么得到树 $T^{\prime}, E$ 减少 $2(l+1)$ ，又因为删去 $v$ 的儿子而使 $E$ 增大 $l$ ，所以 $E$ 的变化值为 $-l-2, I$ 的变化值为 $-l$ 。由归纳假设知，在 $T^{\prime}$ 中，$E^{\prime}=I^{\prime}+2(k-1)$ 。于是再将 $v$ 以及 $v$ 与它的两个儿子的连边加回到 $T^{\prime}$ 中，得到 $T$ ，由于 $E^{\prime}=E-l-2, I^{\prime}=I-l$ ，所以 $E=I+2 k$ 。

同理可证，在正则 $m$ 分树中有 $E=(m-1) I+m i$ ，具体证明留给读者作为习题。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：有根树与二分树

下一篇：最优树

本文对您是否有用？有用 (0) 无用 (0)