一、动机
我们之前已经学习了几种常用的线性数据结构，为什么还要引入树结构？
回顾一下之前学习的数据结构，无论是vector和stack还是list与queue，其中涉及的操作无非是静态操作（如查找）和动态操作（插入、删除等）两种。而对于向量、列表两大线性结构而言，这两种操作各有一种复杂度相对较大。如下图：
树结构结合了列表和向量的优点
树相关描述指标：高度与深度
树的表示——树应该提供的一些接口
父节点表示法的不足——需要改进访问子节点/兄弟节点的复杂度
子节点表示法: 解决了向下查找的问题，但是向上查找复杂度较高
结合父子节点表示法——存储小数据集需要额外O(n)空间
- 父+子表示法美中不足的地方在于，每个节点要存储所有子节点的索引。首先这样需要花费额外的
的空间复杂度，其次各个节点的子数据集长度相差悬殊，显得并不规范。
长子+兄弟表示法
- 每个节点只存储其长子和兄弟两个引用。这样每个节点只需要常数空间，且长度彼此接近。
- 后面将要学习的二叉树的很多实现就是基于长子+兄弟表示法。
二、二叉树
节点度数不超过2的树称为二叉树。对于深度为h的二叉树，节点个数有如下关系:
对于二叉树而言，其高度增长缓慢，宽度增长迅速。
2.1 真二叉树
真二叉树
真二叉树即所有节点的出度均为偶数的二叉树。在实际使用中我们可以将出度不为2的节点通过虚拟的“补0”操作来补充成真二叉树。可以证明这种补充在渐进意义上并不会增加复杂度，但是对于后续的算法会提供很大的便利。
2.2 多叉树
凡是有根且有序的树，都可以用二叉树完全描述。
将普通的树通过长子+兄弟表示法转换为二叉树
- 故接下来研究和实现树相关算法时，都可以仅对二叉树进行研究和实现。
2.3 遍历二叉树
二叉树的几种遍历方法
2.3.1 先序遍历
-
递归实现：
先序遍历的递归实现
既然递归实现的复杂度就是，是不是就已经是最好的算法了呢？这里涉及两个概念：
①“每帧”的复杂度：
假如每个递归实例对应于一帧，但是因为递归要求的通用格式，所以每帧尽管对应常数复杂度，但是这里的常数却不一定足够小。
②尾递归
递归调用出现在整个递归实例体的尾部。这种递归很容易转换为迭代，比如引入一个栈。
此外，迭代实现有助于更清晰地了解整个流程。
先序遍历迭代版本
注意左右孩子的入栈次序。为了先遍历左子树再遍历右子树，我们需要先将右子树压入栈中。
实例分析
先序遍历的迭代版本一看起来非常自然，同时清晰明了。但是这种实现方法很难推广到后面的中序遍历和后序遍历。下面可以尝试一种更通用的思路。
-
左侧链
迭代二版本：利用左侧链展开算法
思路：将二叉树每个局部区域视为一条左侧链，链条上的节点又可以延伸出一个右子树。在遍历时先自顶向下遍历左侧链，然后自底向上逐一访问右子树即可。
脉络
迭代2实现
每沿着左侧链向下一个节点，首先对该节点数据进行访问，然后将该节点的右孩子压入栈中。当当前左侧链访问到最后时（最后一个节点的左子树为空），退出当前左侧链，弹出栈顶的子树根节点，在对新的节点遍历左侧链。
迭代2朱算法
2.3.2 中序遍历
-
还是从递归算法开始：
递归算法
观察
中序遍历思路
遍历思路：
①从根节点开始，沿着左侧链顺序而下，将遇到的每个左子树节点压入栈中；
②遍历完当前左侧链（最后一个节点的左子树为空），随即退出，弹出栈顶元素
③对弹出的栈顶元素进行访问
④以刚访问过的节点为起点，遍历左侧链。
实现
实例分析
2.3.3 层次遍历
若队列不为空，则继续：
①每次循环开始，去除队首的元素进行访问；
②“左顾右盼”，将左子树和右子树加入（如果有的话）队列；
层次遍历实现
层次遍历实例
2.4 树重构
我们知道，给定一棵二叉树，我们可以完全地导出其先序遍历序列、中序遍历序列以及后续遍历序列。那反过来，能否根据这三个序列导出树的拓扑结构呢？
答案是可以的。我们需要先序遍历序列或者后序遍历序列中的一个 + 中序遍历序列，就可以重构出整棵树的拓扑结构。
重构树
网友评论