数据结构严蔚敏版第06章.ppt
93页
第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 1数据结构数据结构第六章第六章 树和二叉树树和二叉树9/3/2024 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 2ABCDEFGHIJKLM树树 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 36.1 6.1 树的类型定义树的类型定义数据对象数据对象D：：D是具有相同特性的数据元素的集合。
是具有相同特性的数据元素的集合数据关系数据关系R：： 若若D为空集，则称为空树；为空集，则称为空树； 否则否则:（（1））在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root,（（2））当当n>1时时，，其其余余结结点点可可分分为为m(m>0)个个互互不不相相交交的的有有限限集集 T1, T2, …, Tm, 其其中中每每一一棵棵子子集集本本身身又又是是一一棵棵符合本定义的树，称为根符合本定义的树，称为根root的子树基本操作：基本操作：查找：查找： Root(T); Value(T, cur_e); Parent(T, cur_e); LeftChild(T, cur_e); TreeEmpty(T); TreeDepth(T); TraverseTree(T, Visit( )); 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 46.1 6.1 树的类型定义树的类型定义插入：插入： InitTree(&T); CreateTree(&T, definition); Assign(T, cur_e, value); InsertChild(&T, &p, i, c);删除：删除： ClearTree(&T); DestroyTree(&T); DeleteChild(&T, &p, i); DestroyTree(&T); 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 56.1 6.1 树的类型定义树的类型定义和线性结构的比较和线性结构的比较 线性结构线性结构 树结构树结构第一个数据元素第一个数据元素(无前驱无前驱)；； 根结点根结点(无前驱无前驱)；；最后一个数据元素最后一个数据元素(无后继无后继)；； 多个叶子结点多个叶子结点(无后继无后继)；；其它数据元素其它数据元素 树中其它结点树中其它结点(一个前驱、一个后继一个前驱、一个后继) 。
(一个前驱、多个后一个前驱、多个后继继) 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 6ABCDEFGHIJKLM树形表示树形表示A (B (E (K, L), F), C(G ), D( H( M), I, J))嵌套括号表示法嵌套括号表示法树的表示方法：树的表示方法： I JFKLGMCCDBEA文氏图文氏图凹入表凹入表ABFEKLCDHIGMJ 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 7基本术语基本术语结点结点: 数据元素数据元素 + 若干指向子树的分支。
若干指向子树的分支结点的度结点的度: 分支的个数分支的个数树的度树的度: 树中所有结点的度的最大值树中所有结点的度的最大值叶子结点叶子结点: 度为零的结点度为零的结点分支结点分支结点: 度大于零的结点；度大于零的结点； 路径路径和和路径长度路径长度孩孩子子结结点点、、双双亲亲结结点点、、兄兄弟弟结结点点、、堂堂兄兄弟弟、、祖祖先先结结点点、、子孙子孙结点边边：双亲节点：双亲节点x到子结点到子结点y的有序对的有序对(x，，y)结结点点的的层层次次: 假假设设根根结结点点的的层层次次为为1，，第第i 层层的的结结点点的的子树根结点的层次为子树根结点的层次为i+1规定根的层数为规定根的层数为0树的深度：树的深度：树中叶子结点所在的最大层次树中叶子结点所在的最大层次 森林：森林：是是m（（m≥0）棵互不相交的树的集合任何一棵）棵互不相交的树的集合任何一棵非空树是一个二元组非空树是一个二元组Tree = （（root，，F））其中：其中：root被称为根结点，被称为根结点，F被称为子树森林被称为子树森林 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 86.2 6.2 二叉树的类型定义二叉树的类型定义二叉树的定义二叉树的定义定义：定义：二叉树是由二叉树是由n(n>=0)个结点的有限集合构个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。
不相交的左右子树组成，并且左右子树都是二叉树与树的关系：与树的关系：这也是一个递归定义这也是一个递归定义区别区别：： 二叉树结点的子树要区分左子树和右二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树子树，还是右子树 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 9(a)空二叉树空二叉树A (b)根和空的根和空的左右子树左右子树AB (c)根和左子树根和左子树二叉树的二叉树的5 5种基本形态种基本形态A(d)根和右子树根和右子树BA (e)根和左右子树根和左右子树BC 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 10二叉树的主要基本操作：二叉树的主要基本操作：查找：查找： Root(T); Value(T, e);Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit());插入：插入： InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);删除：删除： ClearBiTree(&T); DestroyBiTree(&T); DeleteChild(T, p, LR); 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 11性质性质1：： 在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结点个结点(i>=1)。
证明：证明：采用归纳法证明此性质采用归纳法证明此性质当当i=1时，只有一个根结点，时，只有一个根结点，2i-1=20 =1,命题成立命题成立现在假定第现在假定第i－－1层上命题成立，则第层上命题成立，则第i－－1层上至层上至多有多有2i-2个结点由于二叉树每个结点的度最大为个结点由于二叉树每个结点的度最大为2，，故在第故在第i层上最大结点数为第层上最大结点数为第i－－1层上最大结点数的二层上最大结点数的二倍，倍， 即即2×2i-2＝＝2i-1命题得到证明命题得到证明二叉树的重要特性：二叉树的重要特性： 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 12性质性质2：深度为：深度为k的二叉树至多有的二叉树至多有2k－－1个结点（个结点（k>=1).证明：证明：深度为深度为k的二叉树的最大的结点时为二叉的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质树中每层上的最大结点数之和，由性质1得到每层上的得到每层上的最大结点数最大结点数2i-1（（第第i层上的最大结点数）层上的最大结点数）二叉树的重要特性：二叉树的重要特性： 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 13二叉树的重要特性：二叉树的重要特性：性质性质3：： 对任何一棵二叉树，如果其终端结点数为对任何一棵二叉树，如果其终端结点数为n0，，度为度为2的结点数为的结点数为n2，，则则n0＝＝n2＋＋1。
证明：证明：设二叉树中度为设二叉树中度为1的结点数为的结点数为n1，二叉树中总结点，二叉树中总结点数为数为N，因为二叉树中所有结点均小于或等于，因为二叉树中所有结点均小于或等于2，所以有：，所以有：N＝＝n0＋＋n1＋＋n2 （（——1）） 再看二叉树中的分支数，除根结点外，其余结点都再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设有一个进入分支，设B为二叉树中的分支总数，为二叉树中的分支总数， 则有：则有：N＝＝B＋＋1由于这些分支都是由度为由于这些分支都是由度为1和和2的结点射出的，的结点射出的，所以有：所以有：B＝＝n1+2*n2 N＝＝B＋＋1＝＝n1＋＋2×n2＋＋1 （（——2)由式（由式（——1）和（）和（——2）得到：）得到： n0+n1+n2=n1+2*n2+1 n0＝＝n2＋＋1 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 14满二叉树满二叉树2453671123456(a)完全二叉树完全二叉树123457(b)非完全二叉树非完全二叉树12367( c)非完全二叉树非完全二叉树 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 15两种特殊形态的二叉树：两种特殊形态的二叉树： 一棵深度为一棵深度为k且由且由2k-1个结点的二叉树称为个结点的二叉树称为满二叉树满二叉树。
如果深度为如果深度为k、、由由n个结点的二叉树中各结点能够与深个结点的二叉树中各结点能够与深度为度为k的顺序编号的满二叉树从的顺序编号的满二叉树从1到到n标号的结点相对应，标号的结点相对应，则称这样的二叉树为则称这样的二叉树为完全二叉树完全二叉树完全二叉树的特点完全二叉树的特点是：是：（（1）所有的叶结点都出现在第）所有的叶结点都出现在第k层或层或k－－1层2）对任一结点，如果其右子树的最大层次为）对任一结点，如果其右子树的最大层次为h，则，则其左子树的最大层次为其左子树的最大层次为h或或h＋＋1满二叉树和完全二叉树满二叉树和完全二叉树 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 16 性质性质4：具有：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为[log2n]＋＋1。
符号符号[x]表示不大于表示不大于x的最大整数的最大整数 证明：证明：假设此二叉树的深度为假设此二叉树的深度为k，则根据性质，则根据性质2及完全及完全二叉树的定义得到：二叉树的定义得到：2k-1－－1
（（2）如果）如果2i>n，则结点，则结点i为叶子结点，无左孩子；否为叶子结点，无左孩子；否则，其左孩子是结点则，其左孩子是结点2i （（3）如果）如果2i＋＋1>n，则结点，则结点i无右孩子；否则，其右孩无右孩子；否则，其右孩子是结点子是结点2i＋＋1证明：略！证明：略！完全二叉树的特点完全二叉树的特点: : 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 186.3 6.3 二叉树的存储结构二叉树的存储结构1.顺序存储结构顺序存储结构它是用一组连续的存储单元存储二叉树的数据元素它是用一组连续的存储单元存储二叉树的数据元素因此，必须把二叉树的所有结点安排成为一个恰当的序因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：逻辑关系，用编号的方法： #define max-tree-size 100Typedef telemtype sqbitree[max-tree-size];Sqbitree bt 从树根起，自上层至下层，每层自左至右的给所有从树根起，自上层至下层，每层自左至右的给所有结点编号。
结点编号 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 19LKJIHGFEDCBA 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树完全二叉树ABCDEFGHIJKL 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 20ØØØØABCDEFGØ 表示该处没有元素表示该处没有元素存在仅仅为了好理解存在仅仅为了好理解ABCDEØØØØFG一般二叉树一般二叉树 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 211.1.顺序存储结构顺序存储结构缺点：缺点：有可能对存储空间造成极大的浪费，在最坏有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为的情况下，一个深度为H且只有且只有H个结点的个结点的右单支树右单支树确确需要需要2h-1个结点存储空间。
而且，若经常需要插入与删个结点存储空间而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！除树中结点时，顺序存储方式不是很好！ 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 221.1.顺序存储结构顺序存储结构ABCDindexindex 0 01 1 2 23 34 4 5 5 6 6 7 78 8 9 9 1010 1111 1212 1313 1414 1515A AØ ØB BØ Ø Ø Ø Ø ØC CØ ØØ Ø Ø ØØ ØØ ØØ ØØ ØD D- -- -- - 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 23lchildDatarchildAB^^CDE^^F^^G^^H^（（2 2）二叉链表法）二叉链表法ABCDEFGH 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 24Typedef struct BiTNode { TelemType data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree;2 2）二叉链表法）二叉链表法二叉树的二叉链表存储表示二叉树的二叉链表存储表示 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 25Status CreateBiTree(BiTree *T) { /*创建一棵二叉树创建一棵二叉树*/ scanf(&ch); if(ch= =") T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T–>data=ch; CreateBiTree(T–>lchild); CreateBiTree(T–>rchildd); } return OK; }6.3 6.3 二叉树的存储结构二叉树的存储结构链式存储结构的算法：链式存储结构的算法： 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 26三叉链表法三叉链表法ABCDEFGHDBCEF^GH^A^^^^^^^^rchildparentdatalchild 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 27Typedef struct TBiTNode { TelemType data; struct TBiTNode *lchild,*rchild,*parent; } BiTNode,*BiTree;三叉链表法三叉链表法二叉树的三叉链表存储表示二叉树的三叉链表存储表示 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 286.4 6.4 二叉树的遍历二叉树的遍历一、问题的提出一、问题的提出顺顺着着某某一一条条搜搜索索路路径径巡巡访访二二叉叉树树中中的的结结点点，，使使得得每每个结点均被访问一次，而且仅被访问一次。
个结点均被访问一次，而且仅被访问一次访访问问”的的含含义义可可以以很很广广，，如如：：输输出出结结点点的的信信息息等等 对对“二叉树二叉树”而言，可以有三条搜索路径：而言，可以有三条搜索路径：1．先上后下的按层次遍历；．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；．先左（子树）后右（子树）的遍历；3．先右（子树）后左（子树）的遍历．先右（子树）后左（子树）的遍历 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 296.4 6.4 二叉树的遍历二叉树的遍历二、先左后右的遍历算法二、先左后右的遍历算法 先（根）序的遍历算法：先（根）序的遍历算法：若二叉树为空树，则空操作；否则，（若二叉树为空树，则空操作；否则，（1）访问根结点；）访问根结点； （（2）先序遍历左子树；）先序遍历左子树； （（3）先序遍历右子树。
先序遍历右子树中（根）序的遍历算法：中（根）序的遍历算法：若二叉树为空树若二叉树为空树,则空操作；否则则空操作；否则,（（1）中序遍历左子树；）中序遍历左子树；（（2）访问根结点；）访问根结点； （（3）中序遍历右子树中序遍历右子树后（根）序的遍历算法：后（根）序的遍历算法：若二叉树为空树若二叉树为空树,则空操作则空操作;否则否则,（（1）后序遍历左子树；）后序遍历左子树； （（2）后序遍历右子树；）后序遍历右子树； （（3）访问根结点访问根结点 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 306.4 6.4 二叉树的遍历二叉树的遍历示例示例/-ab＋＋cd图图1 (a-b)/(c+d)/bca-+d图图2 a-(b/c+d)/bca-+d图图3 a-b/c+d先序：先序：/-ab+cd中序：中序：a-b/c+d后序：后序：ab-cd+/先序：先序：-a+/bcd中序：中序：a-b/c+d后序：后序：abc/d+-先序：先序：+-a/bcd中序：中序：a-b/c+d后序：后序：abc/-d+分别称为表达式的前缀表示法、中缀表示法和后缀表示分别称为表达式的前缀表示法、中缀表示法和后缀表示法（逆波兰表示法）。
法（逆波兰表示法） 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 316.4 6.4 二叉树的遍历二叉树的遍历三、算法的递归描述三、算法的递归描述 void Preorder (BiTree T, void( *visit)(TElemType& e)){ // 先序遍历二叉树先序遍历二叉树 if (T) {visit(T->data））; // 访问结点访问结点Preorder(T->lchild, visit); // 遍历左子树遍历左子树Preorder(T->rchild, visit); // 遍历右子树遍历右子树}} 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 32void InOrderTraverse (BiTree T, void( *visit)(TElemType &e)){//中序遍历中序遍历if(T){InOrderTraverse (T->lchild, visit); visit(T->data））; // 访问结点访问结点InOrderTraverse (T->rchild, visit);}}void PostOrderTraverse (BiTree T, void( *visit)(TElemType &e)){//后序遍历后序遍历if(T){PostOrderTraverse (T->lchild, visit);PostOrderTraverse (T->rchild, visit); visit(T->data））; // 访问结点访问结点}} 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 33四、先序遍历算法的非递归描述四、先序遍历算法的非递归描述先序遍历的非递归算法。
先序遍历的非递归算法t指向根，指向根，p为指针，指为指针，指向当前结点使用一个堆栈向当前结点使用一个堆栈s（），（），top为栈指针为栈指针 1 if t==NULL 2 then 输出输出 ‘这是一棵空树这是一棵空树’ 3 else p=t，，top=0 4 DO 5 { while p！！=NULL 6 {输出输出 data（（p））; 7 top++;8 if top〉〉n9 then 调用调用 栈满栈满 10 else {s[top]=p，，p=lchild（（p））}}11 if top！！=012 { p=s[top]; top--; p=rchild（（p））}13}while( top==0 && p==null){算法结束算法结束} 6.4 6.4 二叉树的遍历二叉树的遍历四、先序遍历算法的非递归描述四、先序遍历算法的非递归描述1 if t==NULL2 then 输出输出 ‘这是一棵空树这是一棵空树’ 3 else p=t，，top=0 4 DO 5 { while p！！=NULL 6 {输出输出 data（（p））;7 top++;8 if top〉〉n9 then 调用调用 栈满栈满10 else {s[top]=p，，p=lchild（（p））}}11 if top！！=012 { p=s[top]; top--; p=rchild（（p））}13}while( top==0 && p==null){算法结束算法结束}注注:结点旁结点旁的数字是的数字是该结点的该结点的存储地址存储地址二叉树执行先序遍历算二叉树执行先序遍历算法的过程法的过程栈栈 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 35中序遍历的非递归算法中序遍历的非递归算法{中序遍历的非递归算法，使用堆栈中序遍历的非递归算法，使用堆栈s（），（），top为指针，为指针，t指向根，指向根，p为指针，指向当前结点为指针，指向当前结点}1 top=0,p=t2 DO{ 3 while ( p!=NIL ) 4 { top++ 5 if (top>n )6 then 调用调用 栈满栈满7 else {s[top]=p; p=Lchild(p)}}}8 if top!=09 then { p=s[top], top--10 输出输出 data(p) } 11 p<--rchild(p)12 }while (top==0 && p==null);{算法结束算法结束} 输输出出信信息息栈中栈中内容内容过程过程调用调用p的指向的指向p=NIL时，则时，则p〈〈--s（（top））输出输出信息信息栈中栈中内容内容过程过程调用调用p的指的指向向p= NIL时，时，则则p〈〈--s（（top））空空1c9,1 10的右的右*311的左的左2-19的右的右112,1 2的左的左411,1 11的左的左 *114,2,1 4的左的左*4d111的右的右*1a2,1 4的右的右*2-空空1的右的右3+12的右的右533的左的左65,1 5的左的左86,3 6的左的左*68,5,1 8的左的左*8e36的右的右*3B5,1 8的右的右*5/空空7的右的右7*15的右的右977的左的左*79,1 9的左的左10f空空7的右的右^10,9 10的左的左 *10-+/*-abefcd12456738910111 top=0,p=t2 DO{ 3 while ( p!=NIL ) 4 { top++ 5 if (top>n )6 then 调用调用 栈满栈满7 else {s[top]=p; p=Lchild(p)}}}8 if top!=09 then { p=s[top], top--10 输出输出 data(p) } 11 p<--rchild(p)12 }while (top==0 && p==null); 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 37五、遍历算法的应用举例五、遍历算法的应用举例: :1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数(先序遍历先序遍历)void CountLeaf (BiTree T, int& count){ {if ( T ) { {if ((!T->lchild)&& (!T->rchild))count++;CountLeaf( T->lchild, count); // 统计左子树中叶子结点个数统计左子树中叶子结点个数CountLeaf( T->rchild, count);// 统计右子树中叶子结点个数统计右子树中叶子结点个数}} 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 38五、遍历算法的应用举例五、遍历算法的应用举例2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)int Depth (BiTree T ){ {if ( !T ) depthval = 0; else {depthLeft = Depth( T->lchild );depthRight= Depth( T->rchild );depthval = 1+(depthLeft> depthRight? depthLeft:depthRight);} }return depthval;} } 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 39五、遍历算法的应用举例五、遍历算法的应用举例3、复制二叉树、复制二叉树(后序遍历后序遍历)// 生成一个二叉树的结点生成一个二叉树的结点BiTNode *GetTreeNode(TElemType item,BiTNode *lptr , BiTNode *rptr ){ if (!(T = (BiTNode*)malloc(sizeof(BiTNode))))exit(1); T-> data = item; T-> lchild = lptr；； T-> rchild = rptr; return T;} 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 40五、遍历算法的应用举例五、遍历算法的应用举例3、复制二叉树、复制二叉树(后序遍历后序遍历)BiTNode *CopyTree(BiTNode *T){ if (!T )return NULL;if (T->lchild ) newlptr = CopyTree(T->lchild);else newlptr = NULL;if (T->rchild ) newrptr = CopyTree(T->rchild);else newrptr = NULL;newnode = GetTreeNode(T->data, newlptr, newrptr);return newnode;} 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 416.5 6.5 线索二叉树线索二叉树一、何谓线索二叉树？一、何谓线索二叉树？遍历二叉树是按一定的规则将二叉树中结点排列成遍历二叉树是按一定的规则将二叉树中结点排列成一个线性序列；这实际上是把一个非线性结构进行线性一个线性序列；这实际上是把一个非线性结构进行线性化的操作。
化的操作以二叉链表作为存储结构时，对于某个结点只能找以二叉链表作为存储结构时，对于某个结点只能找到其左右孩子，而不能直接得到结点在任一序列中的前到其左右孩子，而不能直接得到结点在任一序列中的前驱或后继要想得到只能通过遍历的动态过程才行驱或后继要想得到只能通过遍历的动态过程才行怎样保存遍历过程中得到的信息呢？怎样保存遍历过程中得到的信息呢？（（1〕〕增加两个指针增加两个指针（（2〕〕利用结构中的空链域，并设立标志即采用如利用结构中的空链域，并设立标志即采用如下的形式：下的形式：lchild ltagdatartagrchild 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 426.5 6.5 线索二叉树线索二叉树何谓线索二叉树？何谓线索二叉树？ 指向该线性序列中的指向该线性序列中的“前驱前驱”和和“后继后继”的的指针指针，称，称作作“线索线索”。
包含包含“线索线索”的存储结构，称作的存储结构，称作“线索链表线索链表”；与其相应的二叉树，称作；与其相应的二叉树，称作“线索二叉树线索二叉树”对线索链表中结点的约定：对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定：在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则若该结点的左子树不空，则lchild域的指针指向其域的指针指向其左子左子树树，且左标志域，且左标志域 ltag的值为的值为0；； 否则，否则，lchild域的指针指向其域的指针指向其“前驱前驱”，且左标志，且左标志ltag的值的值为为1若该结点的右子树不空，则若该结点的右子树不空，则rchild域的指针指向其右子域的指针指向其右子树，且右标志域树，且右标志域rtag的值为的值为0；；否则，否则，rchild域的指针指向其域的指针指向其“后继后继”，且右标志，且右标志rtag的值为的值为1 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 436.5 6.5 线索二叉树线索二叉树0 A 0^1B 00D 1 ^1C 11E 1TADBEC中序序列：中序序列：BCAED 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 446.5 6.5 线索二叉树线索二叉树线索链表的结构描述：线索链表的结构描述：typedef enum { Link, Thread } PointerThr; // Link==0:指针，指针，Thread==1:线索线索typedef struct BiThrNode{TElemType data;struct BiThrNode *lchild, *rchild; // 左右指针左右指针PointerThr LTag, RTag; // 左右标志左右标志} BiThrNode, *BiThrTree; 6.5 6.5 线索二叉树线索二叉树找结点的后继找结点的后继线索化线索化：对二叉树以某种次序遍历使其变为线索二叉树的：对二叉树以某种次序遍历使其变为线索二叉树的过程叫做过程叫做线索化线索化。
下面以下面以中序中序为例看看如何索二叉树中为例看看如何索二叉树中找结点的后继找结点的后继1〕〕树中所有叶子结点和只有左子树的右指针均为线索，树中所有叶子结点和只有左子树的右指针均为线索，直接指示了结点的后继；直接指示了结点的后继；（（2〕〕其他非终端结点的右链均为指针，无法得到后继的信其他非终端结点的右链均为指针，无法得到后继的信息然而根据中序遍历的规律可知，结点的后继应是遍历其右息然而根据中序遍历的规律可知，结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点子树时访问的第一个结点，即右子树中最左下的结点3〕〕反之，在中序线索树中找结点前驱的规律是：若左标反之，在中序线索树中找结点前驱的规律是：若左标志是志是1，则左链为线索，指示其前驱；否则，遍历该结点的左子，则左链为线索，指示其前驱；否则，遍历该结点的左子树时最后访问的结点（左子树中最右下的结点为其前驱树时最后访问的结点（左子树中最右下的结点为其前驱)ABCEIDHF GGKnullnull 6.5 6.5 线索二叉树线索二叉树找结点的后继找结点的后继在在后序线索树后序线索树中找结点中找结点x的后继较复杂，可分三种情况：的后继较复杂，可分三种情况：（（1〕〕若结点若结点x是二叉树的根是二叉树的根,则其后继为空则其后继为空;（（2〕若结点〕若结点x是其双亲的右孩子或是左孩子且其双亲没有是其双亲的右孩子或是左孩子且其双亲没有右子树右子树,则其后继即为双亲结点。
则其后继即为双亲结点3〕〕若结点若结点x是其双亲的左孩子，且其双亲有右子树，则是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历出的第一个结点其后继为双亲的右子树上按后序遍历出的第一个结点由此可见，在后序线索化树上找后继时需知道结点的双亲，由此可见，在后序线索化树上找后继时需知道结点的双亲，因此需要使用三叉链表因此需要使用三叉链表可见，在中序线索二叉树上遍历二叉树，虽然时间复杂度可见，在中序线索二叉树上遍历二叉树，虽然时间复杂度也是也是O(n)，，但常数因子小，且不需要设栈，因此若在某程序中但常数因子小，且不需要设栈，因此若在某程序中需要经常遍历或查找结点在遍历所得线性序列中的前驱和后继，需要经常遍历或查找结点在遍历所得线性序列中的前驱和后继，则应采用线索链表作存储结构则应采用线索链表作存储结构 6.5 6.5 线索二叉树线索二叉树二、线索链表的遍历算法二、线索链表的遍历算法:for ( p = firstNode(T); p; p = Succ(p) )Visit(p);中序线索化链表的遍历算法中序线索化链表的遍历算法:※中序遍历的第一个结点中序遍历的第一个结点 ？？※在中序线索化链表中结点的后继在中序线索化链表中结点的后继 ？？ABCEIDHF GGKnullnull 6.5 6.5 线索二叉树线索二叉树二、线索链表的遍历算法二、线索链表的遍历算法:Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(TElemType e)) {// T指向头结点，头指向头结点，头结点的左链结点的左链lchild指向根结点，头结点的右链指向根结点，头结点的右链rchild，， 指向指向中序遍历的最后一个结点。
中序遍历二叉线索链表表示的中序遍历的最后一个结点中序遍历二叉线索链表表示的二叉树，对每个数据元素调用函数二叉树，对每个数据元素调用函数Visitp = T->lchild; // p指向根结点指向根结点while (p != T) { // 空树或遍历结束时，空树或遍历结束时，p==T while (p->LTag==Link) p = p->lchild; if (!Visit(p->data)) return ERROR;// 访问其左访问其左子树为空的结点子树为空的结点 while (p->RTag==Thread && p->rchild!=T) { p = p->rchild; Visit(p->data); // 访问后继结访问后继结点点} p = p->rchild; // p进至其右子树根进至其右子树根} return OK;} // InOrderTraverse_ThrT-+/*-abe fc d 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 496.5 6.5 线索二叉树线索二叉树三、如何建立线索链表？三、如何建立线索链表？在中序遍历过程中修改结点的左、右指针域，在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的以保存当前访问结点的“前驱前驱”和和“后继后继”信息。
信息遍历过程中，附设指针遍历过程中，附设指针pre,并始终保持指针并始终保持指针pre指向当前访问的、指针指向当前访问的、指针p所指结点的前驱所指结点的前驱 6.5 6.5 线索二叉树线索二叉树三、如何建立线索链表？三、如何建立线索链表？Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) {// 中中序遍历二叉树序遍历二叉树T，，并将其中序线索化，并将其中序线索化，Thrt指向头结点指向头结点if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit (OVERFLOW);Thrt->LTag = Link; Thrt->RTag =Thread; // 建头结点建头结点Thrt->rchild = Thrt; // 右指针回指右指针回指if (!T) Thrt->lchild = Thrt; // 若二叉树空，则左指针回指若二叉树空，则左指针回指else {Thrt->lchild = T; pre = Thrt;InThreading(T); // 中序遍历进行中序线索化中序遍历进行中序线索化pre->rchild = Thrt; pre->RTag = Thread; // 最后一个结点线索化最后一个结点线索化Thrt->rchild = pre; }return OK;} // InOrderThreading void InThreading(BiThrTree p) {if (p) {InThreading(p->lchild); // 左子树线索化左子树线索化if (!p->lchild) { p->LTag = Thread; p->lchild = pre; } // 建前驱线索建前驱线索if (!pre->rchild) { pre->RTag = Thread; pre->rchild = p; } // 建后继线索建后继线索pre = p; // 保持保持pre指向指向p的前驱的前驱InThreading(p->rchild); // 右子树线索化右子树线索化}} // InThreading 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 526.6 6.6 树和森林树和森林一、树的三种存储结构一、树的三种存储结构1. 双亲表示法双亲表示法:在在这这种种表表示示中中，，容容易易找找到到父父结结点点及及其其所所有有的的祖祖先先；；也也能能找找到到结结点点的的子子女女和和兄兄弟弟（（虽虽然然比比较较麻麻烦烦））。
但但它它没没有有表表示示出出结结点点之之间间的的左左右右次次序序，，所所以以无无法法求求树树中中某某个个指指定定结结点的最左子结点和右兄弟结点等基本运算点的最左子结点和右兄弟结点等基本运算ABCDEFGHIJKLM8M5L5K4J4I4H3G2F2E1D1C1B-1A12345678910111213 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 53一、一、树的三种存储结构树的三种存储结构1. 双亲表示法双亲表示法:用一组连续空间存储树的结点，并附设一个指用一组连续空间存储树的结点，并附设一个指示器指示其双亲结点的位置结构类型如下：示器指示其双亲结点的位置结构类型如下：#define MAX_TREE_SIZE 100结点结构结点结构:typedef struct PTNode {/* 树中结点结构树中结点结构 */Elem data; /* 结点中的元素结点中的元素 */int parent; // 双亲位置域双亲位置域} PTNode;树结构树结构:typedef struct {PTNode nodes[MAX_TREE_SIZE];int r, n; // 根结点的位置和结点个数根结点的位置和结点个数} PTree 一、树的三种存储结构一、树的三种存储结构2. 孩子链表表示法孩子链表表示法:ABCDEFGHIJKLM^M^L^K^J^IH^G^FEDCBA12345678910111213234 ^56 ^13 ^78910 ^1112 ^ 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 55一、树的三种存储结构一、树的三种存储结构2、孩子链表表示法、孩子链表表示法:结点表中的每一元素又包含一个子表，存放该结点结点表中的每一元素又包含一个子表，存放该结点的所有子结点。
结点表顺序存放，子表用链接表示，子的所有子结点结点表顺序存放，子表用链接表示，子表中的元素按从左到右的次序存放结构类型如下：表中的元素按从左到右的次序存放结构类型如下：双亲结点结构双亲结点结构typedef struct {Elem data;ChildPtr firstchild; // 孩子链的头指针孩子链的头指针} CTBox;树结构树结构:typedef struct {CTBox nodes[MAX_TREE_SIZE];int n, r; // 结点数和根结点的位置结点数和根结点的位置} CTree;孩子结点结构孩子结点结构:typedef struct CTNode {int child;struct CTNode *next;} *ChildPtr; 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 56一、树的三种存储结构一、树的三种存储结构带双亲的孩子链表表示法带双亲的孩子链表表示法:ABCDEFGHIJKLM222 ^56 ^13 ^78910 ^1112 ^8M5L5K4J4I4H3G2F2E1D1C1B-1A12345678910111213^^^^^^^ 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 57一、树的三种存储结构一、树的三种存储结构3、树的二叉链表、树的二叉链表(孩子孩子-兄弟）存储表示法兄弟）存储表示法typedef struct CSNode{Elem data;struct CSNode *firstchild, *nextsibling;} CSNode, *CSTree;ABCDEFGHIJKLMABCDEKFGHMIJ^^^^^^^^^^^^L^^ 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 58二、树、树林与二叉树的转换二、树、树林与二叉树的转换1、树、树林转换为二叉树、树、树林转换为二叉树由于树和二叉树都可以用二叉链表作存储结构，由于树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介可以导出树与二叉树之间的一则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系。
个对应关系从二叉链表表示的定义可知，任何一棵和树对从二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空这样，若把森林中第应的二叉树，其右子树必空这样，若把森林中第二棵树的根结点看成是第一棵树的兄弟，则可以导二棵树的根结点看成是第一棵树的兄弟，则可以导出森林和二叉树之间的对应关系出森林和二叉树之间的对应关系 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 59二、树、树林与二叉树的转换二、树、树林与二叉树的转换树转换为二叉树树转换为二叉树转换规则：转换规则：步骤：步骤：1.将同父亲的兄弟结点连接；将同父亲的兄弟结点连接；2.对每一个非叶结点只保留第一个孩子链，删对每一个非叶结点只保留第一个孩子链，删除其他孩子的链；除其他孩子的链；3.将树向左旋转将树向左旋转450。
第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 60树转换为二叉树树转换为二叉树事例事例ABEDCHJIGFABEDCHJIGF 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 61树转换为二叉树树转换为二叉树事例事例ABEDCHJIGFABEDCHJIGF 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 622 2、森林转换成二叉树、森林转换成二叉树转换规则：转换规则：如果如果F＝＝{T1, T2, …, Tm}是森林，则可按如下规是森林，则可按如下规则转换成一棵二叉树则转换成一棵二叉树B＝＝{root, LB, RB}。
1））若若F为空，则为空，则B为空树；为空树；（（2）若）若F非空，则非空，则B的根的根root为森林中第一棵树为森林中第一棵树的根的根Root(T1)，，B的左子树的左子树LB是从是从T1中根结点的子树中根结点的子树森林森林F1＝＝{T11, T12,…, T1m1}转换而成的二叉树；其右转换而成的二叉树；其右子树子树RB是从森林是从森林F’＝＝{T2, T3, … , Tm}转换而成的二转换而成的二叉树 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 63 AB E GC D F HI AB E GC DF HIA B E GC D FHI2 2、森林转换成二叉树、森林转换成二叉树 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 643 3、二叉树转换为树、二叉树转换为树转换规则：转换规则：1.对有左子树的所有结点与其左孩子的右链上的对有左子树的所有结点与其左孩子的右链上的所有结点进行连接；所有结点进行连接；2.删除以前所有的旧右链。
删除以前所有的旧右链ABEDCHJIGFABEDCHJIGF 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 654 4、二叉树转换成森林、二叉树转换成森林转换规则：转换规则：如果如果B＝＝{root, LB, RB} 是一棵二叉树，则可按是一棵二叉树，则可按如下规则转换成森林如下规则转换成森林F＝＝{T1, T2, …, Tm}（（1））若若B为空，则为空，则F为空树；为空树；（（2）若）若B非空，则为森林中第一棵树的根非空，则为森林中第一棵树的根Root（（T1）即为）即为 B的根的根root，， T1中根结点的子树森林中根结点的子树森林F1＝＝{T11, T12,…, T1m1} 是有是有B的左子树的左子树LB转换而来的森转换而来的森林；林；F中除中除T1之外的其余树组成的森林之外的其余树组成的森林F’＝＝{T2, T3, … , Tm}是由是由B的右子树转换而成的。
的右子树转换而成的 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 66二叉树转换成森林二叉树转换成森林示例示例A B C FD GE HIA B CFD G E HI 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 67 若树若树T为空为空, 返回；否则返回；否则 访问访问T的根结点；的根结点； 依次先根次序遍历各子树依次先根次序遍历各子树T1、、T2……Tm；；右图遍历结果为：右图遍历结果为：右图遍历结果为：右图遍历结果为：A B D E H I J C F G三、三、 树和森林的遍历树和森林的遍历(1) 先根次序遍历的规则：先根次序遍历的规则：ABEDCHJIGF 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 68 若树若树T为空，返回；否则为空，返回；否则 依次后根次序遍历各子树依次后根次序遍历各子树T1、、T2……Tm；； 访问根结点。
访问根结点右图遍历结果为：右图遍历结果为：右图遍历结果为：右图遍历结果为：D H I J E B F G C A树的遍历树的遍历(2) 后根次序遍历的规则：后根次序遍历的规则：ABEDCHJIGF 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 69 若树若树T为空，返回；否则为空，返回；否则 访问根结点；访问根结点； 若第若第1,……i(i≥1）层结点已被访）层结点已被访问，则从左到右依次访问问，则从左到右依次访问i+1层结点；层结点；右图遍历结果为：右图遍历结果为：右图遍历结果为：右图遍历结果为：A B C D E F G H I J树的遍历树的遍历(3) 广度优先遍历广度优先遍历(层次序遍历层次序遍历) ：：ABEDCHJIGF 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 70 若森林若森林F为空为空, 返回；否则返回；否则 访问访问F的第一棵树的根结点；的第一棵树的根结点； 先根次序遍历第一棵树的子树森林；先根次序遍历第一棵树的子树森林； 先根次序遍历其它树组成的森林。
先根次序遍历其它树组成的森林遍历结果遍历结果：：A B C D E F G H I J森林的遍历森林的遍历(1) 先根次序遍历的规则：先根次序遍历的规则： AB E GC D F HIJ 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 71 若森林若森林F为空，返回；否则为空，返回；否则 中根次序遍历第一棵树的子树森林；中根次序遍历第一棵树的子树森林； 访问访问F的第一棵树的根结点的第一棵树的根结点 中根次序遍历其它树组成的森林；中根次序遍历其它树组成的森林； 遍历结果：遍历结果：B C D A F E H J I G森林的遍历森林的遍历(2) 中根次序遍历的规则：中根次序遍历的规则： AB E GC D F HIJ 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 72 若森林若森林F为空，返回；否则为空，返回；否则 依次遍历各棵树的根结点；依次遍历各棵树的根结点； 依次遍历各棵树根结点的所有子女；依次遍历各棵树根结点的所有子女； 依次遍历这些子女结点的子女结点。
依次遍历这些子女结点的子女结点遍历结果：遍历结果：A E G B C D F H I J森林的遍历森林的遍历(3) 广度优先遍历广度优先遍历(层次序遍历层次序遍历) ：： AB E GC D F HIJ 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 736.7 6.7 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码一、最优树的定义一、最优树的定义结点的路径长度结点的路径长度：从根结点到该结点的路径上分支：从根结点到该结点的路径上分支的数目树的路径长度树的路径长度：树中每个结点的路径长度之和树中每个结点的路径长度之和树的带权路径长度树的带权路径长度：树中所有叶子结点的带权路径：树中所有叶子结点的带权路径长度之和长度之和WPL(T) = ∑ wklk (对所有叶子结点对所有叶子结点)。
在所有含在所有含n个叶子结点、并带相同权值的个叶子结点、并带相同权值的m叉树中，叉树中，必存在一棵其带权路径长度取最小值的树，称为必存在一棵其带权路径长度取最小值的树，称为“最优最优树树” 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 74a<60a<70a<80a<90badpassgeneralgoodexcellentYYYYNNNN例如下面的程序：例如下面的程序：if(a < 60)p = “bad”;else if(a < 70)p = “pass”; else if(a < 80)p = “general”; else if(a <90) p = “good”; elsep = “excellent”; 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 75a<80a<70a<90a<60generalbadpassgoodexcellentYYYYNNN70<=a<8080<=a<9060<=a<70a<60generalgoodpassbadexcellentYYYYNNNN 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 76二、如何构造最优树二、如何构造最优树哈夫曼最早研究出一个带有一般规律的算法哈夫曼最早研究出一个带有一般规律的算法:以二叉树为例以二叉树为例:(1) 根据给定的根据给定的n个权值个权值{w1, w2, …, wn}，构造，构造n棵二棵二叉树的集合叉树的集合F = {T1, T2, …, Tn}，其中每棵二叉树中均只，其中每棵二叉树中均只含一个带权值为含一个带权值为wi的根结点，其左、右子树为空树；的根结点，其左、右子树为空树；(2) 在在F中选取其根结点的权值为最小的两棵二叉树，中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和二叉树根结点的权值为其左、右子树根结点的权值之和;(3) 从从F中删去这两棵树，同时加入刚生成的新树中删去这两棵树，同时加入刚生成的新树;(4) 重复重复(2)和和(3)两步，直至两步，直至F中只含一棵树为止。
中只含一棵树为止 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 77二、如何构造最优树二、如何构造最优树a7b5c2d9e3f11g1h644c2g13f1124e36b511h6a713d920 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 78三三. . 赫夫曼编码赫夫曼编码&在远程通讯中，要将待传字符转换成由二进制的在远程通讯中，要将待传字符转换成由二进制的字符串：字符串：&设要传送的字符为：设要传送的字符为： ABACCDA若编码为：若编码为：A—00 B—01 C—10 D---1100010010101100若将编码设计为长度不等的二进制编码，即让待传字若将编码设计为长度不等的二进制编码，即让待传字符串中符串中出现次数较多的字符采用尽可能短的编码出现次数较多的字符采用尽可能短的编码，则转换，则转换的二进制字符串便可能减少。
的二进制字符串便可能减少 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 79三三. . 赫夫曼编码赫夫曼编码&在远程通讯中，要将待传字符转换成由二进制的在远程通讯中，要将待传字符转换成由二进制的字符串：字符串：&设要传送的字符为：设要传送的字符为： ABACCDA若编码为：若编码为： A—0B—00 C—1D---01 000011010但：但： 0000AAAA ABA BB重码重码关键：关键：要设计长度不等的编码，则必须使任一字符要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀的编码都不是另一个字符的编码的前缀 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 80三三. . 赫夫曼编码赫夫曼编码&设要传送的字符为：设要传送的字符为： ABACCDA若编码为：若编码为： A—0B—110C—10D---1110110010101110ACBD000111采用二叉树设计采用二叉树设计二进制前缀编码二进制前缀编码 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 81三三. . 赫夫曼编码赫夫曼编码& 译码过程译码过程：分解接收字符串：遇：分解接收字符串：遇“0”向左，遇向左，遇“1”向右；一旦到达叶子结点，则译出一个字符，反向右；一旦到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。
复由根出发，直到译码完成 ACBD0001110110010101110ABACCDA 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 82三三. .哈夫曼编码哈夫曼编码在一个字符集中，任何一个字符的编码都不是另一个在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀，这种编码称为字符编码的前缀，这种编码称为前缀编码前缀编码我们可以利用二叉树来设计二进制的前缀编码约定我们可以利用二叉树来设计二进制的前缀编码约定左分支表示字符左分支表示字符‘0’，右分支便是字符，右分支便是字符‘1’，则可以用，则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。
如此得到的编码也是前缀编码点字符的编码如此得到的编码也是前缀编码证明：证明： 假设某一个叶子假设某一个叶子x结点的编码是另一个叶子结点结点的编码是另一个叶子结点y编码的前缀，说明从根结点到叶子结点编码的前缀，说明从根结点到叶子结点y中间需经过结点中间需经过结点x，从而说明，从而说明x有左或右子树，这与有左或右子树，这与x是叶子结点矛盾是叶子结点矛盾 那么现在求最短的二进制编码实际上就是构造哈那么现在求最短的二进制编码实际上就是构造哈夫曼树的过程，由此得到的二进制编码，称夫曼树的过程，由此得到的二进制编码，称哈夫曼编码哈夫曼编码 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 83三三. .哈夫曼编码哈夫曼编码由于由于哈哈夫曼树中没有度为夫曼树中没有度为1的结点的结点(这类树又称严格这类树又称严格的的(strict)(或正则的或正则的)二叉树二叉树)；则一棵有；则一棵有n个叶子结个叶子结点的赫夫曼树共有点的赫夫曼树共有2n-1个结点（因个结点（因n2=n0-1)，可以存储，可以存储在一个大小为在一个大小为2n-1的一维数组中。
的一维数组中 如何选定结构类型？如何选定结构类型？（（1）编码需要从叶子到根）编码需要从叶子到根（（2）译码需要从根到叶子）译码需要从根到叶子&求求Huffman编码：由叶子编码：由叶子→根，若：根，若：（（1）从左分支下去，则分支为）从左分支下去，则分支为“0”；；（（2）从右分支下去，则分支为）从右分支下去，则分支为“1” 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 84c2g13e36b511h6a713d920f11244410100000011111 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 85举例举例& 例：已知某系统在通讯时，只出现例：已知某系统在通讯时，只出现C，，A，，S，，T，，B五种字符，它们出现的频率依次为五种字符，它们出现的频率依次为2，，4，，2，，3，，3，试，试设计设计Huffman 编码。
编码 W（权）（权）={2，，4，，2，，3，，3}，叶子结点个数，叶子结点个数n=5 构造的Huffman树414633 T B84 A22 C S 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 86设计示例：设计示例：& 例：已知某系统在通讯时，只出现例：已知某系统在通讯时，只出现C，，A，，S，，T，，B五种字符，它们出现的频率依次为五种字符，它们出现的频率依次为2，，4，，2，，3，，3，，试设计试设计Huffman编码 由由Huffman树得树得Huffman编码为：编码为：148464220001113301 T B A C S出现频率越大的字符，出现频率越大的字符，其其Huffman编码越短。
编码越短T B A C S00 01 10 110 111 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 876.8 6.8 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码赫夫曼编码的实现赫夫曼编码的实现Typedef struct { unsingned int weight ;(赫夫曼树结点结构权赫夫曼树结点结构权) unsingned int parent, lchild, rchild ;(双亲，左右孩子）双亲，左右孩子）}HTNode,*HuffmaTree;（（动态分配数组存储赫夫曼树）动态分配数组存储赫夫曼树）Typedef char * * HuffmaCode;（（动态分配数组存储赫夫曼动态分配数组存储赫夫曼编码表）编码表） 构造赫夫曼树和求赫夫曼编码的算法如下：构造赫夫曼树和求赫夫曼编码的算法如下：Void HuffmaCoding(HuffmaTree &HT,HuffmaCode &hc,int *w,int n) {（（w存放存放n个字符的权值，构造赫夫曼树个字符的权值，构造赫夫曼树HT，，并求并求出出n个字符的赫夫曼编码个字符的赫夫曼编码hc）） if (n<=1) return ; m =2*n-1; HT = (HuffmanTree)malloc((m+1)* sizeof(HTNode));For(p= HT, i=1; i<=n;++i,++p,++w) *p = {*w,0,0,0}; （（叶子结点叶子结点置初值）置初值）For ( ; i<=m,++i,++p) *p = {0,0,0,0};（（生成树的结点置初值）生成树的结点置初值）For (i=n+1; i<=m; ++i){ （（构造构造HUFFMANTREE）） Select (HT,i – 1, S1,S2);（（在在1到到 i-1的范围内选择双亲域为的范围内选择双亲域为0且且权值最小的两子树权值最小的两子树S1，，S2）） HT[s1].parent =i; HT[S2].parent =i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight;} (下面是求编码）下面是求编码） 构造赫夫曼树和求赫夫曼编码的算法如下：构造赫夫曼树和求赫夫曼编码的算法如下：HC = (HuffmanCode)malloc(n+1) * sizeof( char *)); （（分配头指针分配头指针向量）向量）Cd = (char * )malloc(n* sizeof(char);（（分配求编码空间）分配求编码空间）Cd[n-1] = “ \ 0 ”; （（编码结束符）编码结束符）For (i= 1; i<=n; ++i){ （（逐个符号求编码）逐个符号求编码） start = n – 1;（（编码结束符位置）编码结束符位置） for (c =i, f = HT[i].parent; f ! = 0; c = f, f = HT[f].parent) （（从从叶子结点开始向根）叶子结点开始向根） if (HT[f].lchild = = c) cd[ -- start] = “0”; else cd[--start] = “1” ; HC[i] = (char * )malloc((n – start) * size(char));（（为第为第i个字个字符编码分配空间）符编码分配空间） stcpy(HC[i], &cd[start]);（（从从cd复制编码串到复制编码串到HC）） } free(cd); （（释放空间）释放空间）}// HuffanCoding 23 29 11 145 3 7 81 0 1 1 0 1 0 1 110 1 1 11 1 1 00 0 0111 8 0109 8 0 1 710 15 0 3 411 19 0 8 9 12 29 0 5 1013 42 0 6 11 14 58 0 2 1215 100 0 13 143 7 0 0 04 8 0 0 . 02 29 0 0 05 14 0 0 0 6 23 0 0 07 3 0 0 0 8 11 0 0 01 5 0 0 0构成赫夫曼树构成赫夫曼树 w p lc rc 1 5 0 0 02 29 0 0 03 7 0 0 04 8 0 0 05 14 0 0 0 6 23 0 0 07 3 0 0 0 8 11 0 0 09 0 0 010 0 0 011 0 0 0 12 0 0 013 0 0 0 14 0 0 015 0 0 0生成八棵子树生成八棵子树10109911111212131314141515 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 91本章小结本章小结1. 熟练掌握二叉树的结构特性，了解相应的证明方法。
熟练掌握二叉树的结构特性，了解相应的证明方法2. 熟悉二叉树的各种存储结构的特点及适用范围熟悉二叉树的各种存储结构的特点及适用范围3. 要熟练掌握各种遍历策略的递归和非递归算法，了要熟练掌握各种遍历策略的递归和非递归算法，了解遍历过程中解遍历过程中“栈栈”的作用和状态的作用和状态4. 理解二叉树线索化的实质，熟练掌握二叉树的线索理解二叉树线索化的实质，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的化过程以及在中序线索化树上找给定结点的前驱和后继的方法5. 熟悉树的各种存储结构及其特点，掌握树和森林与熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法二叉树的转换方法6. 学会编写实现树的各种操作的算法学会编写实现树的各种操作的算法7. 了解最优树的特性，掌握建立最优树和哈夫曼编码了解最优树的特性，掌握建立最优树和哈夫曼编码的方法 void main( ){int ………………；； while(1) { printf("请选择操作码请选择操作码:\n"); printf("0:结束结束,1:进栈进栈,2:退栈退栈,3:显示显示:c="); scanf("%d",&c); switch(c) {case 0: exit(0); break; case 1: pushs(stack,top); break; case 2: pops(stack,top);break; case 3: outa(stack,top);break; default: printf("操作码不对，请重新输入操作码不对，请重新输入!\n");break; } } printf("程序结束！再见！程序结束！再见！\n");} 第六章第六章第六章第六章第六章第六章6.1 6.1 树的类树的类型定义型定义 6.2 6.2 二叉树二叉树的类型定义的类型定义 6.3 6.3 二叉树二叉树的存储结构的存储结构 6.4 6.4 二叉树二叉树的遍历的遍历 6.5 6.5 线索二线索二叉树叉树 6.6 6.6 树和森树和森林林 6.7 6.7 哈夫曼哈夫曼树与哈夫曼树与哈夫曼编码编码 93Thank you !Thank you ! 。
