4.树（一）
树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。
树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程
显然，一个结点到它的某个子孙结点有且仅有一条路径。树中结点之间的父子关系具有如下特征：
（1）树中任一结点都可以有零个或多个直接后继(即子结点)，但至多只能有一个直接前驱(即父结点)。
（2）树中只有根结点无前驱，叶结点无后继。
（3）树中某些结点之间具有父-子关系或者祖先-子孙关系，祖先-子孙关系是对父子关系的扩展，一些结点之间，如兄弟结点（同一个父亲的诸子结点被称为兄弟结点）之间就没有这种关系。
树的基本操作
1、判树空：TREEEMPTY(T)
2、求根：ROOT(T)
3、求树的深度：TREEDEPTH(T)
4、求结点的兄弟结点：BROTHER(T, e)
5、求结点的父结点：PARENT(T, e)
6、求结点的子结点：CHILD(T, e, i)
7、建立树：CREATE_TREE(T, T1 , T2 , … , Tm )
8、遍历树：TRAVERSAL(T)
二叉树的特征
① 二叉树每个结点最多有2个子结点；
② 二叉树的子树有左右之分。
二叉树不是树的特殊情况，尽管我们将看到二叉树与树两个概念之间有许多联系，但它却是全然不同于树的另外一个概念。
树与二叉树的主要区别：
⑴ 二叉树中结点的子树分成左子树和右子树，即使某结点只有一棵子树，也要指明该子树是左子树，还是右子树，就是说二叉树是有序的；
⑵ 树决不能为空（换言之树不能为空集），即它至少有一个结点，而一棵二叉树可以是空的（或者说二叉树可以为空集）。
满二叉树的特点是：
① 叶结点都在第k层上；
② 每个分支结点都有两个子结点；
③ 叶结点的个数等于非叶结点个数加1。
具有n个结点高度为k的完全二叉树的特点是：
⑴ 树中只有最下面两层结点的度可以小于2；
⑵ 树中最下面一层的结点都集中在该层最左边的若干位置上（满二叉树意义上）；
⑶ 树中叶结点只能在层数最大的两层上出现，即存在一个非负整数k使得树中每个叶结点或在第k层或第k + 1层上；
⑷ 对树中所有结点，按层次顺序，用自然数从1开始编号，仅仅编号最大的非叶结点可以没有右孩子，其余非叶结点都有两个孩子结点。
5.2.2 二叉树顺序存储
要存储一棵二叉树，必须存储其所有结点的数据信息、左孩子和右孩子地址，既可用顺序结构存储，也可用链接结构存储。
二叉树的顺序存储是指将二叉树中所有结点按层次顺序存放在一块地址连续的存储空间中，同时反映出二叉树中结点间的逻辑关系。
这种顺序存储方式是完全二叉树最简单、最节省空间的存储方式，多数完全二叉树应用算法都采用了这种顺序存储方式。它实际上只存储了结点信息域之值，而未存储其左孩子和右孩子地址，通过计算可找到它的左孩子、右孩子和父结点，寻找子孙结点和祖先结点也非常方便。
但是，这种方法应用到非完全二叉树时，却有很多缺点。如果采用上述的顺序存储方式，按照层次顺序，对非完全二叉树之结点进行编号，则这时的编号不能与结点一一对应。为此，先加入若干虚结点将其转换成一棵“完全二叉树”，然后再对原来的结点和虚结点统一编号，最后完成顺序存储。但这增加了用于存储虚结点的空间。
二叉树的遍历：
按照一定次序访问树中所有结点，并且每个结点仅被访问一次的过程。
树中任一结点 p 都要进栈三次，出栈三次。第一次出栈是为遍历 p 的左子树；
第二次出栈是为遍历 p 的右子树；
第三次出栈是为访问 p .
练习：
已知某二叉树的前序遍历序列是ABDGCEFH，中序遍历序列是DGBAECHF，它的后序遍历序列是什么？
实现：
通过观察发现，在第i层上若结点x在结点y的左边，则x一定在y之前被访问。
并且，在第i+1层上，x的子结点一定在y的子结点之前被访问。
用一个队列来实现。
二叉树层次遍历算法需要一个辅助队列，具体方法如下：
根结点入队。
重复本步骤直至队为空:
若队列非空，取队头结点并访问；
若其左指针不空，将其左孩子入队；
若其右指针不空，将其右孩子入队。
遍历二叉树的应用—复制二叉树
可以按先根遍历、中根遍历或后根遍历的方式复制二叉树。以后根遍历为例进行复制。
复制过程：先复制子结点，再复制父结点，将父结点与子结点连接起来。
例题
1、利用二叉树后序遍历计算二叉树结点个数
二叉树中结点总数 =
左子树结点总数 + 右子树结点总数+ 1（根结点）