数据结构复习（第五章）：树与二叉树

树与二叉树从层次关系到递归结构的一整套理解这一章讨论的主题是树与二叉树。和前面的线性表、串相比这里的结构不再是单一的前后次序而是开始进入层次化组织的世界。一个结点之下可以分出多个后继不同分支之间彼此并列而整棵结构又围绕根结点向下展开。也正因为如此树在数据结构中有非常重要的位置文件目录、组织关系、分类体系、表达式结构以及后面会学到的堆、并查集、搜索树等内容本质上都和树形组织方式密切相关。这一章的内容主线非常清晰。先讲树的基本概念建立结点、层次、度、叶子、路径、深度等基本术语再过渡到二叉树说明二叉树并不只是“度不超过 2 的树”而是一种左右子树有严格区分的递归结构接着讨论二叉树的顺序存储与链式存储再进一步进入遍历问题包括先序、中序、后序和层次遍历最后通过由遍历序列构造二叉树等内容把前面的定义、性质和算法真正串联起来。整体上看这一章最核心的不只是会背结论而是理解“树为什么天然适合递归表示”和“遍历为什么本质上是在规定访问根结点的时机”。一、树的本质一种分层展开的逻辑结构树可以看作由若干结点构成的有限集合。当结点个数为零时它是一棵空树当结点个数大于零时整棵树有且仅有一个根结点其余结点又可以分成若干个互不相交的子树。这个定义看上去简短但里面包含了树最核心的两层含义。第一层含义是“唯一根”。树不是任意连起来的一组结点而必须存在唯一的起点。第二层含义是“递归分解”。一棵树去掉根之后剩余部分并不是杂乱无章的而是若干棵规模更小、结构相同的树。也就是说树的定义本身就带有递归色彩后面所有有关树的存储、遍历和性质分析几乎都建立在这个递归结构之上。和线性结构相比树最明显的差别在于关系类型变了。线性表强调一对一的前驱后继关系而树强调的是一种一对多的层次关系。父结点可以拥有多个孩子结点孩子结点向下又可以继续分支因此树更适合描述带层级的对象集合。二、树的基本术语关键在于把“位置关系”说清楚学习树时最先要过的是术语关。因为树中结点的意义不只是它本身存了什么数据更取决于它位于整棵结构中的什么位置。结点是树中的基本单位。根结点是最顶层的那个结点它没有前驱。结点的子树根称为该结点的孩子结点而这个结点称为孩子结点的双亲结点。具有同一双亲的结点互称兄弟。没有孩子的结点称为叶子结点也叫终端结点至少有一个孩子的结点称为分支结点也叫非终端结点。树中一个结点拥有的子树个数称为该结点的度树的度则是各结点度的最大值。这个概念非常重要因为后面二叉树、m 叉树、满二叉树、完全二叉树等很多定义都和“每个结点最多能分出多少个孩子”直接相关。此外层次、路径、路径长度、结点深度、树的高度这些概念也必须分清。通常把根所在层记作第一层根的孩子在第二层依次向下扩展。两个结点之间沿父子关系依次经过的结点序列称为路径路径上的边数称为路径长度。一个结点的深度是从根到该结点所经历的层级而树的高度则是树中结点层数的最大值。很多选择题和计算题看似在换着花样提问本质都是在问你是否把这些位置概念真正想明白。三、树的性质背后都是“边数、层数、分支数”的关系树这一节最常见的一类问题就是围绕结点总数、边数、层数和度之间的关系进行推导。真正值得掌握的不是零碎结论而是这些结论为什么成立。首先树中结点数如果是 n那么边数一定是 n−1。原因并不复杂除根结点外每个结点都有且仅有一个双亲因此每增加一个非根结点就对应增加一条从双亲到它的边。这个结论极其基础后面会反复使用。其次树中所有结点的度数总和等于边数。因为每一条边都可以理解为某个双亲指向某个孩子因此一条边恰好对应一次“度”的贡献。于是如果把所有结点的度加起来结果恰好就是整棵树的边数也就是 n−1。很多树的计数题本质就是从这个角度切入的。再往下如果已知不同度数的结点个数也可以建立总结点数、叶子数与分支结点数之间的关系。这类题常常会结合“某树是 m 叉树”“某树的结点度只可能为若干种值”“某层恰有多少结点”来出题。做这类题时最稳妥的方法不是凭印象套公式而是先把总结点数与总边数分别表示出来再利用“边数 总度数 n−1”去联立分析。四、二叉树不是一般树的特例那么简单而是一种更严格的结构二叉树经常被误解为“度不超过 2 的树”。这个说法只说对了一部分。更准确地说二叉树是另一类递归定义的结构它或者为空或者由一个根结点以及一棵左子树和一棵右子树组成且左右子树本身也都是二叉树。这里最关键的地方在于“左”和“右”不能颠倒。一般树中孩子之间通常没有固定次序而二叉树中左子树和右子树是有区分的。即使某个结点只带一个孩子这个孩子是左孩子还是右孩子也会构成不同的二叉树。这就是为什么“二叉树并不等价于每个结点度不超过 2 的有序树”的直观根源。正因为左右有别二叉树才会比一般树更适合表达有方向、有顺序的结构。例如表达式树中左子树和右子树分别对应不同运算对象排序树中左子树和右子树承载着不同大小关系遍历序列中不同访问顺序也都依赖于左右子树的严格区分。五、几类典型二叉树要区分的是“形状是否规整”二叉树内部又可以分出多种典型形态其中最常考的是满二叉树、完全二叉树以及二叉排序树、平衡二叉树等概念中的前两种基础形态。满二叉树指的是除叶子结点外每个结点都有两个孩子并且所有叶子都位于同一层的二叉树。它的结构非常规整每一层都被填满因此很多结论都可以直接写成按层累加的形式。若树高为 h则总结点数为 2^h−1第 i 层最多有 2^(i−1) 个结点叶子结点数为 2^(h−1)。完全二叉树则比满二叉树稍微宽松一些。它要求的是除最后一层外其余各层都达到最大结点数而最后一层的结点必须从左到右连续排列。也就是说完全二叉树允许最后一层不满但不能中间有空缺、右边却还有结点。这个“从左到右连续”是判断完全二叉树的关键。很多题之所以容易错就是因为把这两个概念混在一起。满二叉树强调的是每层都满完全二叉树强调的是编号连续、形状尽量靠左。满二叉树一定是完全二叉树但完全二叉树不一定是满二叉树。只要最后一层少几个最右侧结点它依然可能是完全二叉树但已经不是满二叉树了。六、二叉树最重要的性质是按层展开后的数量规律二叉树之所以适合出计算题是因为它的层次结构特别规则很多数量关系都可以直接从按层分析中推出。第一个基本性质是二叉树第 i 层上的结点数最多为 2^(i−1)。因为根只有一个下一层最多 2 个再下一层每个结点最多再分出 2 个所以按层翻倍增长。第二个基本性质是高度为 h 的二叉树最多有 2^h−1 个结点。这个结论就是把每层最多结点数累加得到的结果即 124…2(h−1)2h−1。第三个特别重要的性质是对于任意一棵非空二叉树如果度为 0 的结点个数为 n0度为 2 的结点个数为 n2那么总有 n0n21。这个结论在综合题中极其常见。它背后的原因可以从边数关系推出设度为 1 的结点数为 n1则总结点数 nn0n1n2而边数既等于 n−1也等于 0·n01·n12·n2n12n2两式相等化简即可得到 n0n21。这个结论几乎是解决“已知某类结点个数求叶子数”问题的标准入口。对于完全二叉树还有两条经常和顺序存储结合起来的性质。其一若总结点数为 n则树高为 ⌊log2 n⌋1。其二若按层自上而下、从左到右给结点编号为 1 到 n则编号为 i 的结点其双亲编号为 ⌊i/2⌋左孩子为 2i右孩子为 2i1。这正是顺序存储能够高效表示完全二叉树的根本原因。七、二叉树的存储不只是会写结构体而是理解“结构适合哪种表示”二叉树常见的存储方式有两大类顺序存储和链式存储。顺序存储通常用数组实现。它最适合完全二叉树因为完全二叉树按层编号后基本没有空位数组位置与逻辑结构之间能建立非常自然的对应关系。根放在下标 1 或 0 处都可以只要约定一致就能用简单公式求双亲和孩子位置。这样的表示访问结点非常直接也适合一些只关心位置关系的算法。但如果二叉树比较稀疏顺序存储就会浪费大量空间。因为很多数组单元对应的逻辑位置其实没有结点却仍然得保留出来。这也是为什么顺序存储通常只特别适合完全二叉树而对一般形态的二叉树并不总是理想。链式存储则更通用。二叉链表中的每个结点通常包括数据域、左孩子指针和右孩子指针三个部分。这样无论树是满的、完全的、偏斜的还是形状很不规则都可以用是否为空指针来描述孩子是否存在。链式存储的优势在于结构灵活特别适合一般二叉树的递归处理、遍历和动态构造。从学习角度看这里真正要掌握的是顺序存储利用的是位置规律链式存储利用的是指针关系完全二叉树更偏向前者一般二叉树更偏向后者。不要把“顺序存储二叉树”简单理解为一种默认写法它其实是一种和树形特征高度绑定的特定表示方式。八、遍历的本质不是走一遍而已而是在规定“何时访问根”二叉树遍历是这一章的重心。很多人一开始会把先序、中序、后序背成口号但真正理解它们的关键是抓住一句话三种深度优先遍历的区别不在于左子树或右子树谁先谁后而在于“访问根结点”的时机不同。先序遍历是先访问根再遍历左子树最后遍历右子树。也就是“根—左—右”。中序遍历是先遍历左子树再访问根最后遍历右子树也就是“左—根—右”。后序遍历则是先遍历左子树再遍历右子树最后访问根即“左—右—根”。三者看起来只差一步但表达的结构信息并不一样。先序强调先看到根因此常用于需要优先处理父结点的场景中序把根放在左右子树之间对于二叉排序树会得到有序序列后序则把根放在最后特别适合先处理子问题再合并结果的情形比如删除整棵树、计算子树属性等。这三种遍历都具有明显的递归特征。因为任意一棵二叉树本身就是根、左子树、右子树的组合只要把“遍历一棵树”的问题拆成“遍历左子树”“遍历右子树”再在恰当时机访问根就能自然写出递归算法。换句话说遍历算法之所以看起来简洁并不是因为它技巧性强而是因为它和二叉树的定义本身完全同构。九、层次遍历是另一种思路它按层展开而不是沿递归深入除了先序、中序、后序这些深度优先方式二叉树还有层次遍历。层次遍历按照从上到下、从左到右的顺序访问结点先访问根再访问下一层的所有结点再继续向下推进。和前三种遍历不同层次遍历的核心不在递归而在队列。因为按层访问意味着当访问到某个结点时需要把它的左孩子、右孩子按顺序放到后面等待访问而最先进入等待队列的又应该最先被处理这正好符合队列先进先出的特点。因此层次遍历通常和队列是绑定出现的。从结构理解上说层次遍历体现的是“横向展开”的思路而先序、中序、后序体现的是“纵向递归”的思路。前者更适合描述树的整体层级后者更适合描述子树内部的递归关系。两类遍历结合起来基本就把二叉树最重要的访问方法覆盖完整了。十、由遍历序列确定二叉树关键在于谁能提供根的位置这一章另一个非常核心的内容是根据遍历序列构造二叉树。这里最重要的不是机械操作而是理解不同遍历序列各自提供了什么信息。如果给出先序序列和中序序列就可以唯一确定一棵二叉树。原因在于先序序列的第一个元素一定是根结点而中序序列中根左边的部分一定属于左子树右边的部分一定属于右子树。这样一来左右子树的规模和内容都被划分清楚再在对应子区间中递归处理就能唯一恢复整棵树。同理如果给出后序序列和中序序列也能唯一确定二叉树。因为后序序列的最后一个元素一定是根接下来仍然可以借助中序序列去切分左、右子树再递归构造。但若只给先序和后序一般情况下不能唯一确定一棵二叉树。因为这两种序列虽然都能指出根却不能独立提供左右子树的分界位置尤其当某些结点只有一个孩子时究竟这个孩子是左孩子还是右孩子信息会发生歧义。也就是说真正能起到“切分左右子树”作用的是中序序列。它把根放在中间因此天然携带左右划分信息这正是它在构造题中地位特殊的原因。十一、遍历相关题目的难点不在定义而在能否顺着结构推二叉树遍历题常见有三类。第一类是直接写出某棵二叉树的某种遍历序列。这类题最基本但最容易因为看图急躁而出错。稳妥的方法不是凭感觉跳着看而是严格按“根、左、右”或“左、根、右”的规则一层层递归展开。第二类是已知两种遍历序列恢复树或求第三种遍历序列。这类题本质是对“根在哪里、左右如何切分”的考查。只要抓住根在先序首位、后序末位、中序中间这一点推导路径就会比较清楚。第三类是把遍历和算法功能结合起来例如统计叶子结点数、求树高、交换左右子树、判断结构相似性等。这类题往往不是单纯背遍历而是要求在遍历过程中顺便完成某种计算。它们共同体现了一个重要事实遍历不是目的而是访问结构的一种方式。真正的算法任务通常是在遍历过程中完成信息提取、归纳或更新。十二、这一章特别适合建立递归思维树与二叉树之所以重要不只是因为它们本身常用更因为它们是训练递归思维的最佳入口之一。在线性表里很多操作虽然也能递归描述但顺序结构更容易用循环表达而在树中递归几乎是最自然的语言。定义本身是递归的遍历是递归的求高度、求结点数、判断相似性、交换左右子树等操作也都天然可以递归完成。因为一棵树从整体上看是一个对象从局部上看又由若干棵更小的树组成这种“整体与部分同构”的特性正是递归成立的根本原因。真正学会树不只是记住几个名词和公式更重要的是逐渐形成这样的结构意识当一个问题能分解成若干个同类型的子问题并且子问题之间界限清晰、合并关系明确时递归往往就是最自然的解法。二叉树正好把这一点表现得非常典型。十三、这一章最容易混淆的地方往往都和“区分”有关这一章有几个特别容易混淆的点需要单独拎出来。第一不要把一般树和二叉树混为一谈。二叉树不是“最多两个孩子”这么简单它还要求左右子树有严格区分。第二不要把满二叉树和完全二叉树混为一谈。前者要求所有层都满后者只要求最后一层靠左连续。第三不要把结点的深度、树的高度、路径长度混为一谈。深度是某个结点相对根的位置高度是整棵树的最大层数路径长度则是路径上边的条数。第四不要把先序、中序、后序遍历理解成三套互不相关的规则。它们其实共享同一套“先处理左子树再处理右子树”的框架只是访问根的时机不同。第五不要误以为任意两种遍历都能唯一确定二叉树。真正具有左右切分能力的是中序遍历因此通常需要“中序 先序”或“中序 后序”才行。结语这一章看似从“树的定义”讲起实际却是在把数据结构学习进一步从线性世界推进到层次世界。在线性表中我们更多处理的是相邻关系而在树中我们开始处理父子、兄弟、层次和分支关系。二叉树则在一般树的基础上进一步收紧结构使它既保留层次性又具备更强的递归表达能力。把这一章真正学透之后收获不只是会做几道树的题而是会开始意识到很多复杂对象之所以能被高效组织和处理靠的并不是把它们排成一列而是把它们放进一个层次分明、可递归分解的结构中。到这里数据结构这门课也就真正从“顺序组织数据”走向了“结构化表达问题”。重点问题