树是一个或多个结点组成的有限集合T，有一个特定的结点称为树的根结点，其余的结点被分成m（m≥0）个不相交的集合T1、T2、…、Tm，每一个集合本身又是一棵树，被称为这个根结点的子树。
图5.11所示是一棵具有10个结点的树，结点A为树的根结点，除A之外的其余结点分为3个不相交的集合T1={B，E ，F}、T2={C，G}和T3=｛D，H，I，J｝，形成了结点A的3棵子树，T1、T2和T3本身也分别是一棵树。例如，子树T1的根结点为B，其余结点又分为两个不相交的集合{E}和{F}，它们形成了子树T1的根结点B的两棵子树。

图5.11一棵具有10个结点的树
?? 树的基本术语有：
孩子、双亲、兄弟：树中某结点的各子树的根称为该结点的孩子；相应地该结点称为其孩子的双亲；具有相同双亲的结点互称为兄弟。图5.11中，结点B、C、D都是结点A的孩子，结点A是结点B的双亲，也是结点C、D的双亲，结点B、C、D互为兄弟。
结点的度：一个结点所拥有的子树的个数称为该结点的度。图5.11中，结点A的度为3，结点B的度为2，结点E的度为0。
叶结点、分支结点：度为0的结点称为叶结点，或者称为终端结点；度不为0的结点称为分支结点，或者称为非终端结点。图5.11中，结点A、B、C、D为分支结点，结点E、F、G、H、I、J为叶结点。
结点的层数：规定树的根结点的层数为1，其他任何结点的层数等于它的双亲结点的层数加1。图5.11中，结点A的层数为1，结点B、C、D的层数为2，结点E、F、G、H、I、J的层数为3。
树的深度：一棵树的叶结点的最大层数称为树的深度。图5.11所示的树的深度为3。
二叉树是结点的有限集合，这个有限集合或者为空集（称为空二叉树），或者由一个根结点及两棵不相交的、分别称为这个根的左子树和右子树的二叉树组成。
图5.12所示的是一棵二叉树，根结点为A，其左子树包含结点B、D、G，右子树包含结点C、E、F、H、I。根A的左子树又是一棵二叉树，其根结点为B，有非空的左子树（由结点D、G组成）和空的右子树。根A的右子树也是一棵二叉树，其根结点为C，有非空的左子树（由结点E、H、I组成）和右子树（由结点F组成）。

???

??? 上面介绍的树的基本术语在二叉树中同样适用，但需要说明的是，尽管树和二叉树的概念之间有许多关系，但它们是两个概念。二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树是有序的，二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。例如，图5.13中是四棵不同的二叉树，但如果作为树，它们就是相同的了。
?图5.12二叉树

??? 在树与二叉树之间有一个自然的一一对应的关系，每一棵树都能惟一地转换成它所对应的二叉树。把树转换成对应的二叉树的方法是：将树中所有相邻兄弟用线连起来，然后去掉双亲到子女的连线，只留下双亲到第一个子女的连线。对图5.11所示的树用上述方式处理后稍加倾斜，就得到对应的二叉树，
如图5.14所示。

????????????????????????????? 图5.13四棵不同的二叉树???

??? 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶结点都在同一层上，这样的一棵二叉树称为满二叉树。
完全二叉树：一棵深度为k的有 n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。显然，一棵满二叉树必定是一棵完全二叉树。
在图5.15中，图（a）为一棵满二叉树，图（b）为一棵完全二叉树，图（c）为一棵非完全二叉树。

??????????????????????????????????????????????????????????????????? 图5.14树对应的二叉树

????????
??????????????????? 图5.15满二叉树、完全二叉树和非完全二叉树

## 二叉树的存储结构
?? （1） 顺序存储结构 所谓顺序存储结构，就是用一组连续的存储单元存放二叉树中的结点。完全二叉树由于其结构上的特点，通常采用顺序方式存储。 按从上至下、从左到右的次序将一棵有n个结点的完全二叉树的所有结点从1到n编号，就得到结点的一个线性序列，如同图5.15（b）所示。 从图5.15(b)中我们可以看出，完全二叉树中除最下面一层外，各层都被结点充满了，每一层结点的个数恰好是上一层结点个数的2倍。因此，从一个结点的编号就可以推知它的双亲及左、右孩子结点的编号： 当2i≤n时，结点i的左孩子是2i，否则结点i没有左孩子； 当2i+1≤n时，结点i的右孩子是2i+1，否则结点i没有右孩子； 当i≠1时，结点i的双亲是结点［i/2］。 由于完全二叉树中结点的序号可以惟一地反映出结点之间的逻辑关系，所以可以用一维数组按从上至下、从左到右的顺序存储树中所有结点的数据信息，通过数组元素的下标关系反映完全二叉树中结点之间的逻辑关系。图5.16给出了图5.15(b)所示的完全二叉树的顺序存储示意图（注意由于数组下标从0开始，因此数组元素的下标等于结点在完全二叉树中的序号减1）。 ????????????????????????? 图5.16完全二叉树的顺序存储示意图 ??? 对于一般的二叉树，如果仍按照从上至下、从左到右的顺序将树中的结点 顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系。这时假设将一般二叉树进行改造，增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。在二叉树中假设增添的结点在数组中所对应的元素值为“空”。图5.17给出了图5.15(c)所示的非完全二叉树的顺序存储示意图。 ????????????????????????? 图5.17非完全二叉树的顺序存储示意图 ?? （2） 链式存储结构 二叉树的链式存储结构是用链建立二叉树中结点之间的关系，通常采用的链式存储结构为二叉链表。所谓二叉链表，是将二叉树中的结点设置为如下的结构体类型：
| lchild | data | rchild | |—|—|—|
其中，data表示保存结点本身信息的信息域，lchild和rchild分别为指向结点的左孩子和右孩子的指针域。由于每个结点有两个指针域，所以形象地称之为二叉链表。 当二叉树采用二叉链表存储结构时，如果某结点的左孩子或右孩子不存在，则相应的指针域为空，除此之外，还设置一指针变量指向二叉树的根结点，称之为头指针。与单链表中头指针的作用相似，二叉链表中的头指针 可以惟一地确定一棵二叉树。图5.18给出了图5.15(c)所示的非完全二叉树的二叉链表存储示意图。 图5.18二叉链表存储示意图
## 二叉树的遍历
??? 遍历是二叉树的一种重要运算。二叉树的遍历是指按一定的次序访问二叉树中的每个结点，使每个结点被访问一次且只被访问一次。 根据二叉树的定义知道，一棵二叉树可看做由三部分组成：根结点、左子树和右子树。若规定D、L、R分别表示“访问根结点” 、“遍历根结点的左子树”和“遍历根结点的右子树”，则二叉树的遍历共有六种方式：DLR、LDR、LRD、DRL、RDL、RLD。若又规定按先左子树后右子树的顺序进行遍历，则遍历有三种方式：DLR、LDR和LRD，它们分别被称为前序遍历、中序遍历和后序遍历。另外，还有一种按二叉树中结点由上至下、由左到右的顺序进行遍历的方式，称为层次遍历。 前序遍历的方法为： 若二叉树为空，遍历结束，否则，①访问根结点；②前序遍历根结点的左子树；③前序遍历根结点的右子树。 中序遍历的方法为： 若二叉树为空，遍历结束，否则，①中序遍历根结点的左子树；②访问根结点；③中序遍历根结点的右子树。 后序遍历的方法为： 若二叉树为空，遍历结束，否则，①后序遍历根结点的左子树；②后序遍历根结点的右子树；③访问根结点。 ?? 层次遍历的方法是： 从二叉树的第一层（根结点）开始，从上至下逐层遍历；在同一层中，则按从左到右的顺序对结点逐个访问。 对于图5.12所示的二叉树，按前序遍历方式进行遍历所得到的结果序列为ABDGCEHIF，按中序遍历方式进行遍历所得到的结果序列为DGBAHEICF，按后序遍历方式进行遍历所得到的结果序列为GDBHIEFCA，按层次遍历方式进行遍历所得到的结果序列为ABCDEFGHI。 转载自：http://public.whut.edu.cn/comptsci/web/data/515.htm