数据结构之树与二叉树

一、树的基本概念

1.1树的定义

• 树是 N(N>=0) 个结点的有限集合，N = 0 时，称为空树，这是一种特殊的情况。
• 树适合表示具有层次结构的数据。
• 树中的某个结点（除根结点外）最多只和上一层的一个结点（即其父结点）有直接关系，根结点没有直接上层结点，因此在 n 个结点的树中有 n-1 条边，而树中每个结点预期下一节点的零个或多个结点（即其子女结点）有直接关系。

• 在任意一颗非空树中应满足：
• 有且仅有一个特定的称为根的结点。
• 当 N > 1 时，其余结点可分为 m(m>0) 个互不相交的有限集合 T1，T2，T3，···，Tm，其中每一个集合本身又是一棵树，并且称为根节点的子树。

• 树的结构是递归的，是一种递归的数据结构，树作为一种逻辑结构，同时也是以一种分层结构，具有以下两种特点：
• 树的根结点没有前驱结点，除根结点之外的所有结点有且仅有一个前驱结点。
• 树中所有的根结点可以有零个或多个后继结点。

1.2 基本术语

• 考虑某个结点 K，根 A 到结点 K 的唯一路径上的任意节点，称为结点 K 的祖先结点。若结点 B 是结点 K 的祖先结点，则结点 K 是结点 B 的子孙结点。路径上最接近结点 K 的结点 E 称为 K 的双亲结点，而 K 为结点 E 的孩子结点。根结点 A 是树中唯一没有双亲的结点，有相同双亲的结点称为兄弟节点，如若结点 K 与结点 L 有相同的结点 E ，则称 K 和 L 为兄弟结点。
• 树中一个结点的子结点个数称为该结点的度，树中结点的最大度数称为树的度。
• 度大于 0 的结点称为分支结点（又称非终端结点）；度为 0 （没有子女结点）的结点称为叶子结点（又称终端结点）。在分支结点中，每个结点的分支数就是该结点的度。
• 结点的层次是从树根开始定义，根结点为第 1 层（有些教材将根结点定义为第 0 层），它的子结点为第 2 层，以此类推。
• 结点的深度是从根结点开始自顶向下逐层累加的。
• 结点的高度是从叶结点开始自底向上逐层累加的。
• 树的高度（又称深度）是树中结点的最大层数。
• 有序树和无序树：树中结点的子树从左到右是有序的，不能交换，这样的树叫做有序树，有序树中，一个结点其子结点按从左到右顺序出现是有关联的。反之则称为无序树。
• 路径和路径长度：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。
• 注意：由于树中的分支是有向的，即从双亲结点指向孩子结点，所以树中的路径是从上到下的，同一双亲结点的两个孩子结点之间不存在路径。
• 森林：森林是 m(m>=0) 棵互不相交的树的集合。森林的概念与树十分相似，只要把树的根结点删去就成了森林。反之，只要给 n 棵独立的树加上一个结点，并把这 n 棵树作为该结点的子树，则森林就成了树。

1.3 树的性质

• 树中的结点数等于所有结点的度数加 1。
• 度为 m 的树中第 i 层上至多有 m^(i-1) 个结点（ i>=1）。
• 高度为 h 的 m 叉树至多有（ m^h - 1）/（ m -1 ）个结点。
• 具有 n 个结点的 m 叉树的最小高度为 [ log m（ n*(m-1) + 1 ）]。

二、二叉树的概念

2.1 二叉树的定义

• 二叉树是另一种树形结构，其特点是每个节点至多只有两棵子树（即二叉树中不存在度大于 2 的结点），而且，二叉树的子树有左右之分，其次序不能颠倒。

• 与树相似，二叉树也以递归的形式定义，二叉树是 n(n>=0) 个结点的有限集合：
• 1）或者为空二叉树，即 n = 0;
• 2）或者是由一个根结点和两个互不相交的被称为根的左子树和右子树组成，左子树和右子树分别是一棵二叉树。
• 二叉树是有序树，将其左右子树颠倒，就成为了另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。

• 二叉树与度为 2 的有序树的区别：
• 1）度为 2 的树至少有 3 个结点，而二叉树可以为空。
• 2）度为 2 的有序树的孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为 2 均需确认其左右次序，也就是说二叉树的结点次序不是相对于另一个节点而言，而是确定的。

2.2 几个特殊的二叉树

• 满二叉树：一棵高度为 h，并且含有 2^h - 1 个结点的二叉树称为满二叉树，即树中的每一层都含有最多的结点。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点外每个结点的度数均为 2。
• 可以对满二叉树按层序进行编号：约定编号从根结点（根结点编号为 1）起，自上而下，自左向右。这样每个结点对应一个编号，对于编号为 i 的结点，如果有双亲，则双亲为 [ i/2 ] ，如果有左孩子，则左孩子为 2i，右孩子为 2i + 1。

• 完全二叉树：设一个高度为 h，有 n 个结点的二叉树，当且仅当其每一个结点都与高度为 h 的满二叉树中编号为 1~n 的结点一一对应，称为完全二叉树。
• 若 i<=[n/2]，则结点 i 为分支结点，否则为叶子结点。
• 叶子结点只可能在层次最大的两层上出现，对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
• 如果有度为 1 的结点，只可能有一个，且该结点只有左孩子而无右孩子。
• 按层序编号后，一旦出现某个结点（其编号为 i ）为叶子结点或只有左孩子，则编号大于 i 的结点均为叶子结点。
• 若 n 为奇数，则每个分支结点都有左孩子和右孩子；若 n 为偶数，则编号最大的分支结点（编号为 n/2）只有左孩子，没有有子女，其余分支结点左、右子女都有。

• 二叉排序树：一棵空心树，或者是具有性质的二叉树：左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均小于根结点的关键字。左子树和右子树又各是一棵二叉排序树。

• 平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过 1。

2.3 二叉树的性质

• 非空二叉树上叶子结点数等于度为 2 的结点数加 1，即 N0 = N2 + 1;
• N0 + N1 + N2 = N1 + N2 + N2 + 1;
• 非空二叉树的第 K 层上至多有 2^(k-1) 个结点（K>=1)。
• 高度为 H 的二叉树至多有 2^H - 1 个结点（H>=1)。
• 具有 N(N>0) 个结点的完全二叉树的高度为 [log(N+1)] 或 [log N] + 1。

• 对完全二叉树按从上到下、从左到右的顺序依次编号 1，2，···，N，则有以下关系：
• 1）当 i>1 时，结点 i 的双亲结点编号为 [i/2]，即当 i 为偶数时，其双亲结点的编号为 i/2，它是双亲结点的左孩子。
• 2）当 2i<=N 时，结点 i 的左孩子编号为 2i，否则无有孩子。
• 3）当 2i<=N 时，结点 i 的右孩子编号为 2i+1，否则无右孩子。
• 4）结点 i 所在层次（深度）为 [log i] + 1。

三、二叉树的存储结构

3.1 顺序存储结构

• 二叉树的顺序存储结构就是一组地址连续的存储单元依次自上至下，自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号 i 的结点元素存储在某个数组下标为 i-1 的分量中，然后通过一些方法确定结点在逻辑上的父子和兄弟关系。
• 依据一般的二叉树，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样即能最大程度的节省空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及节点之间的关系。
• 但对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。然而，在最坏的情况下，一个高度为 H 且只有 H 个结点的单支数却需要占据接近 2^H-1 个存储单元。

3.2 链式存储结构

• 二叉链表至少包含 3 个域：数据域 data、左指针域 lchild、右指针域 rchild。
• 在含有 n 个结点的二叉链表中含有 n+1 个空链域。

四、二叉树的遍历

4.1 二叉树的遍历

• 先序遍历、中序遍历、后序遍历、递归算法与非递归算法的转换、层序遍历、由遍历序列构造二叉树。