文章目录
前言
1、树的递归定义
2、树的相关术语
3、树的常见表示形式
4、树的抽象数据类型定义
二、二叉树
1、二叉树的递归定义
2、二叉树的抽象数据类型定义
2、二叉树的性质（包含练习）
3、二叉树的存储结构
（1）二叉树的顺序存储结构
（2）二叉树的链式存储结构
三、遍历二叉树
1、遍历问题
2、按层次遍历二叉树
3、按先左后右遍历二叉树
4、二叉树遍历的递归算法
5、中序遍历非递归算法
6、遍历算法的应用举例
7、练习
四、线索二叉树
1、基本概念
2、查找前驱和后继
3、遍历线索二叉树
4、二叉树的线索化（建立线索链表）
5、练习
五、树和森林
1、树的存储结构
2、树、森林与二叉树的转换
3、树和森林的遍历
六、哈夫曼树及其应用
1、最优二叉树（哈夫曼树）
2、哈夫曼编码、译码
3、存储及算法实现
总结
前言
本文主要介绍数据结构（C语言版）第六章 树与二叉树的内容。主要包括了树的定义和基本术语、二叉树、遍历二叉树、线索二叉树、树和森林以及哈夫曼树及其应用。
其中重难点在于掌握二叉树的基本概念、性质和存储结构以及二叉树的前、中、后序遍历方法，还有哈夫曼树的实现方法与编码和译码的方法，最后就是理解森林与二叉树的转换和树的遍历。
一、树的定义和基本术语
1、树的递归定义
树（Tree）是n（n≥0）个结点的有限集，它或为空树（n=0）；或为非空树，对于非空树T：
●有且仅有一个称之为根的结点；
●除根结点以外的其余结点可分为m（m>0）个互不相交的有限集T1,T2,……,Tm,其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。
注：树的定义具有递归性，即树中还有树。
2、树的相关术语
根——即根结点（没有前驱）
叶子——即终端结点（没有后继）
森林——指m棵不相交的树的集合（例如删除A后的子树个数）
有序树——结点各子树从左至右有序，不能互换（左为第一）
无序树——结点各子树可互换位置。
结点——包含一个数据元素及若干指向其子树的分支
结点的度——结点拥有的子树数
结点的层次——从根到该结点的层数（根结点算第一层）
终端结点——即度为0的结点，即叶子
分支结点——即度不为0的结点（也称为非终端结点）
内部结点——除根结点之外的分支结点树的度——所有结点度中的最大值
树的深度（或高度）——指所有结点中最大的层数
思考：只有一个根结点的树，叶子结点几个？分支结点和内部结点呢？【1,0,0】
双亲——即上层的那个结点（直接前驱）
孩子——即下层结点的子树的根（直接后继）
兄弟——同一双亲下的同层结点（孩子之间互称兄弟）
堂兄弟——即双亲位于同一层的结点（但并非同一双亲）
祖先——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点子孙
3、树的常见表示形式 4、树的抽象数据类型定义
特点：一对多（1：n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。
基本操作：
InitTree(&T); 操作结果：构造空树T。 TreeEmpty(T); 初始条件：树T存在。 操作结果：若T为空树，则返回TRUE,否则FALSE。 DestroyTree(&T); 初始条件：树T存在。 操作结果：销毁树T。 TreeDepth(T); 初始条件：树T存在。 操作结果：返回T的深度。 CreateTree(&T, definition); 初始条件：definition给出树T的定义。 操作结果：按definition构造树T。 Root(T); 初始条件：树T存在。 操作结果：返回T的根。 ClearTree(&T); 初始条件：树T存在。 操作结果：将树T清为空树。 Value(T, cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：返回cur_e的值。 Assign(T, &cur_e, value); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：结点cur_e赋值为value。 Parent(T, cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空” LeftChild(T, cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空” RightSibling(T, cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。 InsertChild(&T,&p, i,c); 初始条件：树T存在，P指向T中某个结点，1≤i≤p所指结点的度+1，非空树c与T不相交。 操作结果：插入c为T中p指结点的第i棵子树。 DeleteChild(&T, &p, i); 初始条件：树T存在，P指向T中某个结点，1≤i≤p指结点的度。 操作结果：删除T中P所指结点的第i棵子树。 TraverseTree(T, Visit()); 初始条件：树T存在，Visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数Visit()一次且至多一次。一旦visit()失败，则操作失败。
明确两点：
（1）普通树（即多叉树）若不转化为二叉树，则运算很难实现。
（2）二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！（遍历——指每个结点都被访问且仅访问一次，不遗漏不重复）。
本章重点：二叉树的表示和实现
二、二叉树
1、二叉树的递归定义
二叉树(Binary Tree)是n (n≥0)个结点所构成的集合，它或为空树（n=0）；或为非空树，对于非空树T：
（1）有且仅有一个称之为根的结点；
（2）除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树
和右子树，且左、右子树本身又都是二叉树。
二叉树实质：是度为2的有序树
二叉树基本特点：
- 每个结点最多有两棵子树（不存在度大于2的结点）；
- 左子树和右子树次序不能颠倒（有序树）
二叉树的五种不同形态
2、二叉树的抽象数据类型定义
ADT Binary Tree{
数据对象D：D是具有相同特性的数据元素的集合。
数据关系R：若D=Φ，则R=Φ；
若D≠Φ，则R={H}；存在二元关系：
①root唯一//关于根的说明
②Dj∩Dk=Φ//关于子树不相交的说明
③ ……//关于数据元素的说明
④ ……//关于左子树和右子树的说明
基本操作P：//至少有20个
}ADT BinaryTree
CreateBiTree(&T,definition)
初始条件；definition给出二叉树T的定义。
操作结果：按dcfinition构造二叉树T。
PreOrderTraverse(T)
初始条件：二叉树T存在。
操作结果：先序遍历T，对每个结点访问一次。
InOrderTraverse(T)
初始条件：二叉树T存在。
操作结果：中序遍历T，对每个结点访问一次。
PostOrderTraverse(T)
初始条件：二叉树T存在。
操作结果：后序遍历T，对每个结点访问一次。
2、二叉树的性质（包含练习）
性质1：在二叉树的第i（i>=1）层上至多有2的k次方-1个结点
证明思路：数学归纳法
- 第1层至多有一个结点
- 第k+1层的结点至多是第k层结点的两倍（k>0)
性质2：深度为k（k>=1）的二叉树至多有2的k次方-1个结点
证明思路：用求等比级数前k项和的公式
性质3：对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2+1（即n0=n2+1）
实际意义：叶子数=2度结点数+1
性质1：在二叉树的第i（i>=1）层上至多有2的k次方-1个结点
证明思路：数学归纳法
- 第1层至多有一个结点
- 第k+1层的结点至多是第k层结点的两倍（k>0)
性质2：深度为k（k>=1）的二叉树至多有2的k次方-1个结点
证明思路：用求等比级数前k项和的公式
性质3：对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2+1（即n0=n2+1）
实际意义：叶子数=2度结点数+1
特殊形态的二叉树
满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-l层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。
性质4：具有n个结点的完全二叉树的深度必为[log2n]+1
性质5：对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i+1；其双亲的编号必为i/2。
练习
3、二叉树的存储结构
（1）二叉树的顺序存储结构
#define MAX_TREE_SIZE100//二叉树的最大结点数
typedef TElemType SqBiTree[MAX_TREE_SIZE];//0号单元存储根结点
SqBitTree bt;
#define MAX_TREE_SIZE100//二叉树的最大结点数 typedef TElemType SqBiTree[MAX_TREE_SIZE];//0号单元存储根结点 SqBitTree bt;
【约定】用一组连续的存储单元依次自上而下、从左到右存储完全二叉树上的结点元素，即：
①完全二叉树：将编号为i的结点元素存储在一维数组中下标为i-1的分量中。
②一般二叉树：将每个结点与完全二叉树上的结点相对照，存储在相应分量中。（以0表示不存在此结点）
特点：
优点：结点间关系蕴含在其存储位置中
缺点：可能对存储空间造成极大的浪费，最坏的情况下，一个深度为k且只有k个结点的右单支树却需要2k-1个结点的存储空间。
适于存满二叉树和完全二叉树
