第三章 树和二叉树

【考纲解析与应试指导】

树和二叉树历来都是考试的重难点章节，从这章开始就从对线性结构的研究过渡到对树形结构的研究，这一章学习的好坏直接关系到在数据结构这门考试中能否能得高分。这一章知识点很多，处处都是可以出题的地方，而且都是大题，鉴于今年的情况，数据结构也许只有两个大题，基本上应该是树和图这两个里面出个大题，查找和排序里出个大题。
这一章是每年必考的地方，建议大家认真复习每一个知识点，重点是二叉树的遍历及其应用，难点是利用树的有关知识设计出有效算法解决树和二叉树的应用问题。

【核心考点】

 树的定义和性质
 二叉树的概念、性质和实现
 遍历二叉树和线索二叉树
 树和森林
 哈夫曼树及其应用
 树的计数

【知识点精讲】

3.1 树的概念

树（Tree）是n（n≥0）个有限数据元素的集合。当n＝0时，称这棵树为空树。在一棵非树T中：
(1). 有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。
(2). 若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，...，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，...，Tm称为这个根结点的子树。
可以看出，在树的定义中用了递归概念，即用树来定义树。因此，树结构的算法类同于二叉树结构的算法，也可以使用递归方法。

树具有下面两个特点：
(1). 树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。
(2). 树中所有结点可以有零个或多个后继结点。

3.2 二叉树

3.2.1 二叉树的定义及其主要特征

二叉树（Binary Tree）是n个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。因此二叉树具有五种基本形态。

二叉树的相关概念如下：
(3). 结点的度。结点所拥有的子树的个数称为该结点的度。
(4). 叶结点。度为0的结点称为叶结点，或者称为终端结点。
(5). 分枝结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。
(6). 左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点
的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。
(7). 路径、路径长度。如果一棵树的一串结点n1,n2,...,nk有如下关系：结
点ni是ni+1的父结点（1≤i(8). 祖先、子孙。在树中，如果有一条路径从结点M到结点N，那么M
就称为N的祖先，而N称为M的子孙。
(9). 结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的
双亲结点的层数加1。
(10). 树的深度。树中所有结点的最大层数称为树的深度。
(11). 树的度。树中各结点度的最大值称为该树的度。
(12). 满二叉树。
(13). 完全二叉树。

二叉树的主要性质：
性质1 一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。
该性质可由数学归纳法证明。证明略。
性质2 一棵深度为k的二叉树中，最多具有2k－1个结点。
性质3 对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有:
n0＝n2＋1。
性质4 具有n个结点的完全二叉树的深度k为[log2n]+1。
性质5 对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：
(1). 如果i>1，则序号为i的结点的双亲结点的序号为i/2("/"表示整除)；如果
i＝1，则序号为i的结点是根结点，无双亲结点。
(2). 如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i>n，则
序号为i的结点无左孩子。
(3). 如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i
＋1>n，则序号为i的结点无右孩子。
此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为（i－1）/2，左孩子的编号为2i＋1，右孩子的编号为2i＋2。

>" src="http://i1.w.hjfile.cn/doc/200811/32502.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/32502.gif">>" src="http://i1.w.hjfile.cn/doc/200811/26508.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/26508.gif">>" src="http://i1.w.hjfile.cn/doc/200811/52955.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/52955.gif">>" src="http://i1.w.hjfile.cn/doc/200811/71602.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/71602.gif">>" src="http://i1.w.hjfile.cn/doc/200811/11087.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/11087.gif">