#269. 第十节 树

第十节 树

在实际生活中，描述数据元素之间逻辑关系的问题不仅仅局限于线性结构，例如家庭、行政组织机构等都是非线性的数据结构。树就是一种非线性的数据结构。

一、树的定义

树作为一种非线性的数据结构，是由 n (n≥0) 个结点组成的有限集合。

  1. 如果 n 为 0 时，树为空树；

  2. 如果 n>0 时，树有一个特定的结点作为根结点。

    根结点只有直接后继，没有直接前驱。除根结点以外的其他结点划分为 m (m≥0) 个互不相交的有限集合 T1，T2， … ，Tm-1，每个集合是一棵树，称为根结点的子树。树的示例如下：

二、树的相关概念

1. 树的度

结点拥有的子树的数量为结点的度，度为 0 的结点是叶结点，度不为 0 的结点为分支结点，树的度定义为树的所有结点中度的最大值。

2. 树的前驱和后继

除根结点没有前驱外，其余每个结点都有唯一一个前驱结点，称为前驱结点；每个结点可以有 0 或多个后继结点。结点的直接后继称为结点的孩子，结点的直接前驱的结点称为结点的父亲。结点的孩子的孩子称为结点的孙子，结点的祖先称为子孙的祖先。同一个双亲子之间互称兄弟。

3. 树中结点的层次

树中根结点为第 1 层，根结点的孩子为第 2 层，依次类推。树中结点的最大层次称为树的深度或高度。

4. 森林

是由 n(n>=0) 棵互不相交的树组成的集合。

三、树的性质

  1. 除根结点没有父结点外，其余结点有且仅有一个父结点。

  2. n 个结点的树，有且仅有 n-1 条边。

  3. 树中任意两个结点之间有且仅有一条简单路径（指路径上的顶点都不相同的路径，不存在自环和重边）。

四、二叉树

二叉树（binary tree，简写 BT）是一种度数为 2 的树，即二叉树的每个结点最多有两个子结点。每个结点的子结点分别称为左孩子、右孩子，它的两棵子树分别称为左子树、右子树。

1. 二叉树的遍历

所谓的遍历是指按一定的规律和次序访问树中的各个结点，而且每个结点仅被访问一次。遍历一般按照从左到右的顺序，共有 4 种遍历方法：前序遍历、中序遍历、后序遍历、层次遍历。

(1) 先序遍历：先访问根结点，再访问左子树，最后访问右子树。 (2) 后序遍历：先左子树，再右子树，最后访问根结点。 (3) 中序遍历：先左子树，访问根结点，最后右子树。 (4) 广度遍历：每一层从左到右访问每一个结点。

例题 1 求下图所示树的各种遍历结果。

  • 先序遍历结果：A B E F C G I D H J L M N
  • 中序遍历结果：E B F A D G C I H J M L N
  • 后序遍历结果：E F B G I C H J D N M L A
  • 层次遍历结果：A B C D E F G H I J L M N

例题 2 关于前面讲的表达式树，我们可以分别用先序、中序、后序的遍历方法得出完全不同的遍历结果，如对于下图遍历结果如下，它们正好对应表达式的 3 种表示方法。

  • 前缀表示、波兰式：+a* b- c/ d e f
  • 中缀表示：(a + b * (c - d) - e / f)
  • 后缀表示、逆波兰式：a b c d - * + e f /

结论：已知前序序列和中序序列可以确定出二叉树；已知中序序列和后序序列也可以确定出二叉树；但已知前序序列和后序序列却不可以确定出二叉树。

例题 3：有二叉树中序序列为 ABCEFGHD，后序序列为 ABFHGEDC。请画出此二叉树，并求前序序列。

解答：根据后序序列知根节点为 C。 因此左子树为：中序序列为 AB，后序序列为 AB； 右子树为：中序序列为 EFGHD，后序序列为 FHGED； 依次推得该二叉树的结构图（如下图）

前序序列为：C B A D E F G H D

例题 4：已知结点的前序序列为 CBADEGFH，中序序列为 ABCDEFGH，构造出二叉树。

2. 二叉树的性质

性质 1：在二叉树的第 i 层上最多有 2i−12^{i-1}个结点 (i≥1)。

证明：很简单，用归纳法。当 i=1 时，2i−1=20=12^{i-1} = 2^0 = 1 显然成立；现在假设第 i-1 层时命题成立，即第 i-1 层上最多有 2i−2 2^{i-2} 个结点。由于二叉树的每个结点的度最多为 2，故在第 i 层上的最大结点数为第 i-1 层的 2 倍，即 2∗2i−2=2i−1 2 * 2^{i-2} = 2^{i-1} 。

性质 2：深度为 k 的二叉树至多有 2k−12^k - 1 个结点 (k≥1)。

证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质 1 可得，深度为 k 的二叉树的结点数至多为 20+21+...+2k−1=2k−1 2^0 + 2^1 + ... + 2^{k-1} = 2^k - 1 ，故命题正确。

特别的，一棵深度为 k 且有 2k−12^k - 1 个结点的二叉树称为满二叉树。如图 A 为深度为 4 的满二叉树，这种树的特点是每层上的结点数都是最大结点数。

可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，从左到右，由此引出完全二叉树的定义：深度为 k，有 n 个结点的二叉树当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 到 n 的结点一一对应时，称为完全二叉树。

下图 B 就是一个深度为 4，结点数为 12 的完全二叉树。它有如下特征：

  • 叶结点只可能在层次最大的两层上出现。
  • 对任意结点，若其右分支下的子孙的最大层次为 m，则在其左分支下的子孙的最大层次必为 m 或 m+1。

下图 C、D 不是完全二叉树，请大家思考为什么？

性质 3：对任意一棵二叉树，如果其叶结点数为 n0，度为 2 的结点数为 n2，则所有结点的度数均不大于 2，所以结点总数（记为 n）应等于 0 度结点数 n0 = n2 + 1。

证明：因为二叉树中所有结点（n）等于 0 度结点数（n0）、1 度结点数（n1）和 2 度结点数（n2）之和，即 n = n0 + n1 + n2。另一方面，1 度结点有一个孩子，2 度结点有两个孩子，故二叉树中孩子结点总数是 n1 + 2n2。树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为 n = n1 + 2n2 + 1。由上述推导得到 n0 = n2 + 1。

例题 1：有 n 个结点的二叉树，已知叶结点个数为 n0，写出度为 1 的结点的个数的计算公式；若此树是度为 k 的完全二叉树，写出 n 为最小的公式；若二叉树中仅有度为 0 和度为 2 的结点，写出求该二叉树结点数 n 的公式。

解答：

  1. 记度为 2 的结点个数为 n2，则 n = n0 + n1 + n2，又因为除了根结点以外，其余结点均由父结点发出，所以 n1 = n + 1 - 2n0。
  2. 当树是深度为 k 的完全二叉树时，n 的最小值 nmin = 2k−12^k - 1。
  3. 当二叉树中仅有度为 0 和度为 2 的结点时，n = n0 + n2，n = 2n2 + 1，所以 n0 = n2 + 1，n = 2n0 - 1。

性质 4：具有 n 个结点的完全二叉树的深度为 floor(log2n)+1floor(log_2n) + 1。

证明：假设深度为 k，根据完全二叉树的定义，前面 k-1 层是满的，所以 n > 2k−1−12^{k-1} -1。但 n 又要满足 n ≤ 2^k - 1。所以 2^(k-1) -1 < n ≤ 2^k - 1。变换一下得到 2^(k-1) ≤ n < 2^k。以 2 为底取对数得到：k - 1 ≤ log2n < k。因为 k 是整数，所以 k = floor(log2n)+1floor(log_2n) + 1。

性质 5：具有 n 个结点的二叉树的高度至少为 log2(n+1)log_2(n+1)。

证明：根据“性质 2”可知，高度为 k 的二叉树最多有 2^k - 1 个结点。反之，对于包含 n 个节点的二叉树，其高度至少为 log2(n+1)log_2(n+1)。

性质 6：对于一棵具有 n 个结点的完全二叉树的任一结点（编号为 i），有以下关系：

  1. 如果 i = 1，则结点 i 为根，无父结点；如果 i > 1，则其父结点编号为 i/2。
  2. 如果 2i > n，则结点 i 无左孩子，否则左孩子编号为 2i；如果 2i+1 > n，则结点无右孩子，否则右孩子编号为 2i+1。

证明：略，我们只要验证一下即可，总结如下图：

例题 2：已知一棵完全二叉树共有 892 个结点，试求：

  1. 树的高度；
  2. 叶子结点数；
  3. 单支结点数；
  4. 最后一个非终端结点的序号。

解答：

  1. 已知深度为 k 的二叉树至多有 2k−12^k-1 个结点（k>1），由于 2^10-1 < 892 < 211−12^11-1，所以树的高度为 10。
  2. 对完全二叉树来说，度为 1 的结点只能是 0 或 1。
    • 设 n1=0，则 892 = n0 + 0 + n2 = n2 + 1 + n2 = 2n2 + 1，因而得到的 n2 不为整数。
    • 设 n1=1，则 892 = n0 + 1 + n2 = n2 + 1 + n2 = 2n2 + 2，得到 n2 = 445，带入 n0 = n2 + 1，得到 n0 = 446，故叶子结点数为 446。
  3. 由 (2) 可知单支结点数为 1。
  4. 对有 n 个结点的完全二叉树，最后一个树叶结点，即序号为 n 的叶结点其双亲结点 n/2，即为最后一个非终端结点，也即序号为向下取整(892/2)=446。此外，由 (2) 可知 n2 = 445，n1 = 1，n = 1，则最后一个非终端结点的序号为 n2 + 1 = 446。

四、习题

  1. NOIP2013 已知一棵二叉树有 10 个节点，则其中至多有()个节点有 2 个子节点。

{{ select(1) }}

  • 4
  • 5
  • 6
  • 7
  1. NOIP2013 已知一棵二叉树有 2013 个节点，则其中至多有()个节点有 2 个子节点。

{{ select(2) }}

  • 1006
  • 1007
  • 1023
  • 1024
  1. NOIP2011 如果根节点的深度记为 1，则一棵恰有 2011 个叶节点的二叉树的深度最少是()

{{ select(3) }}

  • 10
  • 11
  • 12
  • 13
  1. NOIP2010 如果树根算是第一层，那么一颗 n 层的二叉树最多有()个节点。

{{ select(4) }}

  • 2n−12^n-1
  • 2n2^n
  • 2n+12^n+1
  • 2n+1
  1. NOIP2009 一个包含 n 个分支节点（非叶节点）的非空二叉树，它的叶节点数目最多为？

{{ select(5) }}

  • 2n+1
  • 2n-1
  • n-1
  • n+1
  1. NOIP2009 最优前缀编码，也称 Huffman 编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。

{{ select(6) }}

  • (00，01，10，11)
  • (0，1，00，11）
  • (0，10，110，111）
  • (1，01，000，001)
  1. NOIP2011 现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由4 个汉字“之 ”、“乎 ”、“者 ”、“也 ”组成，它们出现的次数分别为 700、600、300、200。那么，“也 ”字的编码长度是多少？

{{ select(7) }}

  • 1
  • 2
  • 3
  • 4
  1. NOIP2016 一棵二叉树如下图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的节点（根节点的下标为 1，若某节点的下标为 i ，则其左孩子位于下标 2i 处、右孩子位于下标(2i+1)处)，则图中所有节点的最大下标为()。

{{ select(8) }}

  • 6
  • 10
  • 12
  • 15
  1. NOIP2016 给定一棵二叉树，采用链式存储方式，每个节点包括节点的数据、左孩子指针、右孩子指针。如果没有左孩子或者右孩子，则对应的为 NULL 指针。那么该链表中空指针的数目为()

{{ select(9) }}

  • 6
  • 7
  • 12
  • 14
  1. NOIP2010 完全二叉树的顺序存储方案，是指将完全二叉树的节点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根节点存放在数组的 1 号位置上，则第 k 号节点的父节点如果存在的话，应当存放在数组中的() 号位置。

{{ select(10) }}

  • 2k
  • 2k+1
  • k/2（下取整）
  • (k+1)/2
  1. NOIP2008 完全二叉树共有 2*N-1 个节点，则它的叶节点数是()。

{{ select(11) }}

  • N-1
  • N
  • 2N
  • 2N-1
  1. NOIP2009 一个包含 n 个分支节点（非叶节点）的非空满 k 叉树，k>=1。它的叶节点数目为()。

{{ select(12) }}

  • nk+1
  • nk-1
  • (k+1)*n-1
  • (k-1)*n+1
  1. NOIP2015 如果根的高度为 1，具有 61 个节点的完全 k 叉树的高度为()

{{ select(13) }}

  • 5
  • 6
  • 7
  • 8
  1. NOIP2014 一棵具有 5 层的满二叉树中节点数为()

{{ select(14) }}

  • 31
  • 32
  • 33
  • 16
  1. NOIP2008 根节点深度为 0，一棵深度为 h 的满 k(k>1)叉树，即除最后一层无任何子节点外，每一层上的所有节点都有 k 个子节点的树，共有()个节点。

{{ select(15) }}

  • (kh+1−1)/(k−1) (k^{h+1}-1)/(k-1)
  • kh−1 k^{h-1}
  • kh k^h
  • (kh−1)/(k−1) (k^{h-1})/(k-1)
  1. NOIP2013 二叉树的()第一个访问的节点是根节点。

{{ select(16) }}

  • 先序遍历
  • 中序遍历
  • 后序遍历
  • 以上都是
  1. NOIP2013 二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值，小于其右子树上所有节点的值。那么，二叉查找树的()是个有序序列。

{{ select(17) }}

  • 先序遍历
  • 中序遍历
  • 后序遍历
  • 宽度优先遍历
  1. 前序遍历序列与中序遍历序列相同的二叉树为()

{{ select(18) }}

  • 根节点无左子树的二叉树
  • 根节点无右子树的二叉树
  • 只有根节点的二叉树或非叶子节点只有左子树的二叉树
  • 只有根节点的二叉树或非叶子节点只有右子树的二叉树
  1. NOIP2015 前序遍历序列与后序遍历序列相同的二叉树为()。

{{ select(19) }}

  • 非叶子节点只有左子树的二叉树
  • 只有根节点的二叉树
  • 根节点无右子树的二叉树
  • 非叶子节点只有右子树的二叉树
  1. NOIP2015 右图是棵二叉树，它的先序遍历是()。

{{ select(20) }}

  • ABDEFC
  • DBEFAC
  • DFEBCA
  • ABCDEF
  1. NOIP2012 如果一棵二叉树的中序遍历是 BAC，那么它的先序遍历不可能是()。

{{ select(21) }}

  • ABC
  • CBA
  • ACB
  • BAC
  1. NOIP2016 表达式 a*(b+c)-d 的后缀表达式是()。

{{ select(22) }}

  • abcd*+-
  • abc+*d-
  • abc*+d-
  • -+*abcd
  1. NOIP2018 表达式 ad-be 的前缀形式是()。

{{ select(23) }}

  • ad* bc* -
  • -* ad* bc
  • a* d-b* c
  • -** adbc
  1. NOIP2010 前缀表达式+3*2+5 12 的值是()。

{{ select(24) }}

  • 23
  • 25
  • 37
  • 65
  1. NOIP2008 一棵二叉树 T，已知其先根遍历是 1243578（数字为节点的编号，以下同），根遍历是 2415736，则该二叉树的后根遍历是()。

{{ select(25) }}

  • 4257631
  • 4275631
  • 7425631
  • 4276531
  1. NOIP2010 一棵二叉树的前序遍历序列是 A B C D E F G，后序遍历序列是 C B F E D G A，则根节点的左子树的节点个数可能是()。

{{ select(26) }}

  • 2
  • 3
  • 4
  • 5
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  3. Powered by Hydro v5.0.1 Community, Modified by CQZYM