中铁建设集团有限公司门户网站,wordpress 4.5.3 漏洞,沈阳网站制作机构,十大广告设计公司简介文章目录 5.1 树的基本概念5.1.1 树的定义5.1.2 森林的定义5.1.3 树的术语5.1.4 树的表示 5.2 二叉树5.2.1 二叉树1. 定义2. 特点3. 性质引理5.1#xff1a;二叉树中层数为i的结点至多有 2 i 2^i 2i个#xff0c;其中 i ≥ 0 i \geq 0 i≥0。引理5.2#xff1a;高度为k的二叉… 文章目录 5.1 树的基本概念5.1.1 树的定义5.1.2 森林的定义5.1.3 树的术语5.1.4 树的表示 5.2 二叉树5.2.1 二叉树1. 定义2. 特点3. 性质引理5.1二叉树中层数为i的结点至多有 2 i 2^i 2i个其中 i ≥ 0 i \geq 0 i≥0。引理5.2高度为k的二叉树中至多有 2 k 1 − 1 2^{k1}-1 2k1−1个结点其中 k ≥ 0 k \geq 0 k≥0。引理5.3设T是由n个结点构成的二叉树其中叶结点个数为 n 0 n_0 n0度数为2的结点个数为 n 2 n_2 n2则有 n 0 n 2 1 n_0 n_2 1 n0n21。 5.1 树的基本概念
5.1.1 树的定义
一棵树是结点的有限集合T 若T非空则 有一个特别标出的结点称作该树的根记为root(T)其余结点分成若干个不相交的非空集合T1, T2, …, Tm (m0)其中T1, T2, …, Tm又都是树称作root(T)的子树。 T 空时为空树记作root(T)NULL。
5.1.2 森林的定义 一个森林是0棵或多棵不相交非空树的集合通常是一个有序的集合。换句话说森林由多个树组成这些树之间没有交集且可以按照一定的次序排列。在森林中每棵树都是独立的具有根节点和子树树与树之间没有直接的连接关系。 森林是树的扩展概念它是由多个树组成的集合。在计算机科学中森林也被广泛应用于数据结构和算法设计中特别是在图论和网络分析等领域。
5.1.3 树的术语
父亲parent、儿子child、兄弟sibling、后裔descendant、祖先ancestor度degree、叶子节点leaf node、分支节点internal node结点的层数路径、路径长度、结点的深度、树的深度
参照前文【数据结构】树与二叉树一树森林的基本概念父亲、儿子、兄弟、后裔、祖先、度、叶子结点、分支结点、结点的层数、路径、路径长度、结点的深度、树的深度
5.1.4 树的表示
【数据结构】树与二叉树二树的表示C语言树形表示法、嵌套集合表示法、嵌套括号表示法 、凹入表示法
5.2 二叉树
5.2.1 二叉树
1. 定义 二叉树是一种常见的树状数据结构它由结点的有限集合组成。一个二叉树要么是空集被称为空二叉树要么由一个根结点和两棵不相交的子树组成分别称为左子树和右子树。每个结点最多有两个子结点分别称为左子结点和右子结点。
2. 特点 二叉树的特点是每个结点最多有两个子结点并且子结点的位置是有序的即左子结点在前右子结点在后。这种有序性使得二叉树在搜索、排序等算法中有广泛的应用。 在二叉树中根结点是整个树的起始点通过根结点可以访问到整个树的其他结点。每个结点都可以看作是一个独立的二叉树它的左子树和右子树也是二叉树。 二叉树可以是空树也可以是只有根结点的树或者是由多个结点组成的树。每个结点可以包含一个数据元素以及指向左子结点和右子结点的指针。 二叉树的形状可以各不相同它可以是平衡的或者不平衡的具体取决于结点的分布情况。在二叉树中每个结点的左子树和右子树都是二叉树因此可以通过递归的方式来处理二叉树的操作。
3. 性质 引理5.1二叉树中层数为i的结点至多有 2 i 2^i 2i个其中 i ≥ 0 i \geq 0 i≥0。 这个引理表明二叉树的每一层上的结点数量是指数级增长的。 引理5.2高度为k的二叉树中至多有 2 k 1 − 1 2^{k1}-1 2k1−1个结点其中 k ≥ 0 k \geq 0 k≥0。 这个引理说明了二叉树的高度与结点数量之间的关系高度越大结点数量也越多。 引理5.3设T是由n个结点构成的二叉树其中叶结点个数为 n 0 n_0 n0度数为2的结点个数为 n 2 n_2 n2则有 n 0 n 2 1 n_0 n_2 1 n0n21。 这个引理描述了二叉树中叶结点和度数为2的结点之间的关系即叶结点的数量比度数为2的结点数量多1。
引理5.1二叉树中层数为i的结点至多有 2 i 2^i 2i个其中 i ≥ 0 i \geq 0 i≥0。 证明使用数学归纳法。
基础步骤 当 i 0 i0 i0 时仅有一个根结点其层数为0。因此第0层上至多有 2 0 1 2^01 201 个结点。因此当 i 0 i0 i0 时引理成立。
归纳假设 假设当 i j ij ij ( j ≥ 0 ) (j\geq0) (j≥0) 时二叉树中第 j j j 层上至多有 2 j 2^j 2j 个结点。
归纳步骤 考虑第 j 1 j1 j1 层上的结点个数。对于任意一个结点其子结点个数最多为2。根据归纳假设第 j j j 层上至多有 2 j 2^j 2j 个结点。因此第 j 1 j1 j1 层上的结点个数最多为 2 × 2 j 2 j 1 2\times2^j2^{j1} 2×2j2j1 个结点。 因此根据数学归纳法对于任意非负整数 i i i二叉树中层数为 i i i 的结点至多有 2 i 2^i 2i 个。
证毕
引理5.2高度为k的二叉树中至多有 2 k 1 − 1 2^{k1}-1 2k1−1个结点其中 k ≥ 0 k \geq 0 k≥0。 对于高度为k的二叉树我们可以计算每一层的最大结点数并将它们相加来得到总结点数的上界。根据引理5.1第 i i i层上至多有 2 i 2^i 2i个结点。那么第 0 0 0层至第 k k k层的结点数上界可以表示为 2 0 2 1 2 2 . . . 2 k 2^0 2^1 2^2 ... 2^k 202122...2k 这是一个等比数列的和可以使用等比数列求和公式进行计算。等比数列的求和公式为 S a ∗ ( r n − 1 ) / ( r − 1 ) S a * (r^n - 1) / (r - 1) Sa∗(rn−1)/(r−1)
其中S表示数列的和a是首项r是公比n是项数。 在我们的情况下首项a1公比r2项数nk1。将这些值代入公式中我们可以得到 2 0 2 1 2 2 . . . 2 k 1 ∗ ( 2 k 1 − 1 ) / ( 2 − 1 ) 2 k 1 − 1 2^0 2^1 2^2 ... 2^k 1 * (2^{k1} - 1) / (2 - 1) 2^{k1} - 1 202122...2k1∗(2k1−1)/(2−1)2k1−1
因此高度为k的二叉树中至多有2^(k1) - 1个结点。
证毕
问题1高度为k (k≥1)的二叉树中至少有多少个结点k1问题2含有k (k≥1)个结点的二叉树高度至多为多少 k-1
引理5.3设T是由n个结点构成的二叉树其中叶结点个数为 n 0 n_0 n0度数为2的结点个数为 n 2 n_2 n2则有 n 0 n 2 1 n_0 n_2 1 n0n21。 设T是由 n n n个结点构成的二叉树其中叶结点个数为 n 0 n_{0} n0次数为2的结点个数为 n 2 n_{2} n2。 根据引理5.3的前提条件我们有以下等式 n n 0 n 1 n 2 ( 5 − 1 ) n n_{0} n_{1} n_{2} (5-1) nn0n1n2 (5−1)
其中 n 1 n_{1} n1是T中次数为1的结点个数。 另一方面设二叉树T的边的个数为 E E E。除了根结点外每个结点和其父结点之间都有且仅有一条边即一个结点对应一条边。因此结点的个数 n n n比边的个数 E E E多1根结点不对应边即 n E 1 ( 5 − 2 ) n E 1 (5-2) nE1 (5−2) 另外从另一个角度来看次数为1的结点对应一条边次数为2的结点对应两条边。因此边的个数 E E E可以表示为 E n 1 2 n 2 ( 5 − 3 ) E n_{1} 2n_{2} (5-3) En12n2 (5−3) 我们将(5-1)、(5-2)和(5-3)联立起来通过求解这个方程组我们可以得到 n 0 n 2 1 n_{0} n_{2} 1 n0n21即二叉树T中的叶结点个数 n 0 n_{0} n0为次数为2的结点个数 n 2 n_{2} n2加1。
证毕
