发布时间 : 星期六 文章数据结构-朱二周更新完毕开始阅读
(a)按根、左和右子树三部分进行遍历。遍历二叉树的顺序存在下面6种可能： TLR（根左右）, TRL（根右左） LTR（左根右）, RTL（右根左） LRT（左右根）, RLT（右左根）
其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。 先序遍历：
若二叉树为空，则结束遍历操作；否则 访问根结点； 先序遍历左子树； 先序遍历右子树。
中序遍历：
若二叉树为空，则结束遍历操作；否则 中序遍历左子树； 访问根结点； 中序遍历右子树。
（3）后序遍历
若二叉树为空，则结束遍历操作；否则 后序遍历左子树； 后序遍历右子树； 访问根结点。
（b）按层次遍历二叉树。实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。 （5）线索二叉树
对二叉树的遍历存在如下问题：
遍历算法要比线性表更复杂、更费时；
为检索或查找二叉树中某结点在某种遍历下的后继，必须从根开始遍历，直
到找到该结点及后继；
如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度。 线索：n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针，这种附加的指针称为“线索” (Thread)。 线索二叉树：加上了线索的二叉链表称为线索链表。相应的二叉树称为线索二叉树。(Threaded Binary Tree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。 线索链表的结点结构：线索链表中的结点结构为 Lchild Ltag Data Rtag Rchild 其中：ltag和rtag是增加的两个标志域，用来区分结点的左、右指针域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。 二叉树的线索化
线索化实质：将二叉树变为线索二叉树的过程称为线索化。按某种次序将二叉树线索化的实质是：按该次序遍历二叉树，在遍历过程中用线索取代空指针。 （6）树的存储结构
双亲表示法：假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲在链表中的位置。类型定义：
#define MAX_TREE_NODE_SIZE 100 typedef struct {
TEntryType info;
int parent;
} ParentNode; typedef struct {
ParentNode item[MAX_TREE_NODE_SIZE]; int n; //树中当前的结点数目
}ParentTree;
树的双亲表示法主要描述的是结点的双亲关系。这种存储方法的特点是寻找结点的双亲很容易，但寻找结点的孩子比较困难。
孩子表示法：由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，此时链表中的结点可以有如下两种结点格式： Data Child1 Child2 ? Childd
Data Degree Child1 Child2 ? childd
在C语言中，这种存储形式定义如下：
#define MAX_TREE_NODE_SIZE 10 typedef struct ChildNode{
int child; //该孩子结点在一维数组中的下标值 struct ChileNode *next; //指向下一个孩子结点
}CNode;
typedef struct{
TEntryType info; //结点信息
CNode *firstchild; //指向第一个孩子结点的指针
}TNode;
typedef struct {
TNode item[MAX_TREE_NODE_SIZE]; int n,root;
//n为树中当前结点的数目，root为根结点在一维数组中的位置
}ChildTree;
这种存储结构的特点是寻找某个结点的孩子比较容易，但寻找双亲比较麻烦，所以，在必要的时候，可以将双亲表示法和孩子表示法结合起来，即将一维
数组元素增加一个表示双亲结点的域parent，用来指示结点的双亲在一维数组中的位置。
孩子兄弟表示法：也称二叉树表示法，或二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。孩子兄弟表示法也是一种链式存储结构。它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系，其结点结构为： Firstchild Item nestsibling 其中，firstchild为指向该结点第一个孩子的指针，nextsibling为指向该结点的下一个兄弟，item是数据元素内容。在C语言中，这种存储形式定义如下：
typedef struct CSNode{
EntryType item;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree; （7）森林与二叉树的转换
（a）树、森林转换成二叉树
将一棵树转换成二叉树的方法：将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。 将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依依地进行转换。 （b）二叉树还原成树或森林
这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。 （8）树和森林的遍历
先根(次序)遍历树： 若树不空，则先访问根结点，然后依次从左到右先根遍历
根的各棵子树；
后根(次序)遍历树：若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点；按层次遍历:若树不空，则自上而下自左至右访问树中每个结点。 森林是树的集合，由此可以对森林中的每一棵树依次从左到右进行先根遍历或者后根遍历。又森林中的（第一棵树的根）、（第一棵树的子树森林）及（其余树构成的森林），分别对应为（二叉树的根）、（二叉树的左子树）和（二叉树的右子树）。由此可如下定义森林的这两种遍历。
（a）先序遍历森林 若森林不空，则可依下列次序进行遍历
访问森林中第一棵树的根结点； 先序遍历第一棵树中的子树森林；
先序遍历除去第一棵树之后剩余的树构成的森林。
（b）中序遍历森林 若森林不空，则可依下列次序进行遍历：
中序遍历第一棵树中的子树森林； 访问森林中第一棵树的根结点；
中序遍历除去第一棵树之后剩余的树构成的森林。 （9）哈夫曼树及其应用
（a）最优二叉树（哈夫曼树）
在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。在路径上的分支数目被称为路径长度。用公式可表示为：
n
WPL??wklk k?1带权的路径长度最小的二叉树称为哈夫曼二叉树或最优二叉树。 构造哈夫曼树的过程：
（1）将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具
有n棵二叉树的森林{T1,T2,...,Tn}，其中每棵二叉树只有一个根结点；
（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新
二叉树，新二叉树的根结点权值为这两棵树根的权值之和；
（3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，
并将刚刚新构造的二叉树加入到森林中； （4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树
就是哈夫曼树。
（b）哈夫曼编码
在传送电文时，希望总长尽可能的短。如果对每个字符设计长度不等的编码，且让电文中出现次数最多的字符采用尽可能短的编码，则传送电文的总长便可减少。此时则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。而设计总长最短的二进制前缀编码即为以n中字符出现的频率作权，设计一棵哈夫曼树的问题。由此得到的二进制前缀编码便称为哈夫曼编码。 （二）基本要求
(1) 熟练掌握二叉树的结构特性或性质，了解相应的证明方法；
(2) 熟悉二叉树的各种存储结构的特点及适用范围；
(3) 熟练掌握二叉树的遍历。不仅要熟练掌握各种遍历策略的递归和非递归
算法，了解遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其它操作。另外，层次遍历是按另一种搜索策略进行的遍历。
(4) 理解线索二叉树的实质是建立结点与其在相应序列中的前驱或后继之间
的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。
(5) 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。
树的存储结构是进行其它操作的基础，应熟练掌握树的孩子兄弟表示法及其上的各种操作(如树的遍历)。
(6) 了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。 （三）重点、难点