树与二叉树课件

1、树与二叉树1数据结构课程的内容数据结构课程的内容树与二叉树2第第6章章 树和二叉树（树和二叉树（ Tree & Binary Tree ）6.1 树的基本概念树的基本概念6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 赫夫曼树及其应用赫夫曼树及其应用特点：特点：非线性结构，一个直接前驱，但可能有多个非线性结构，一个直接前驱，但可能有多个直接后继（直接后继（1 1：n n）树与二叉树36.1 树的基本概念1. 树的定义树的定义2 若干术语若干术语3. 逻辑结构逻辑结构4.存储结构存储结构5. 树的运算树的运算树与二叉树41. 树的定义树的定

2、义注注1：过去许多书籍中都定义树为过去许多书籍中都定义树为n1，曾经有，曾经有“空树不是空树不是树树”的说法，但现在树的定义已修改。的说法，但现在树的定义已修改。注注2：树的定义具有树的定义具有递归性递归性，即树中还有树。，即树中还有树。由一个或多个由一个或多个( (n0n0) )结点组成的有限集合结点组成的有限集合T T，有，有且仅有且仅有一个结点称为根一个结点称为根（rootroot），），当当n1n1时，其余的时，其余的结点分为结点分为m(m0)m(m0)个个互不相交互不相交的有限集合的有限集合T1,T2T1,T2，TmTm。每个集合本身又是棵树，被称作这个根的。每个集合本身又是棵树，被

3、称作这个根的子树子树 。树与二叉树5树的表示法有几种：树的表示法有几种：图形表示法图形表示法嵌套集合表示法嵌套集合表示法广义表表示法广义表表示法目录表示法目录表示法左孩子右兄弟表示法左孩子右兄弟表示法这些表示法的示意图这些表示法的示意图参见教材参见教材P120P120树的抽象数据类型定义树的抽象数据类型定义参参见教材见教材P118-119P118-119树与二叉树6图形表示法：图形表示法：教师教师学生学生其他人员其他人员20032003级级 20042004级级 20052005级级20062006级级河南大学河南大学物理系物理系计算机系计算机系化学系化学系叶子叶子根根子树子树树与二叉树7广义

4、表表示法广义表表示法( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作为根作为由子树森林组成的由子树森林组成的表的名字写在表的左边表的名字写在表的左边datalink 1 link 2.link n麻烦问题：应当开设多少个链域麻烦问题：应当开设多少个链域?树与二叉树8左孩子右兄弟表示法左孩子右兄弟表示法数据数据左孩子左孩子 右兄弟右兄弟( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )树与二叉树9 树的抽象数据类型定义树的抽象数据类型定义（见教材（见教材P1

5、18-119P118-119）ADT Tree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT Tree若若D为空集，则称为空树；为空集，则称为空树；/允许允许n=0若若D中仅含一个数据元素，则中仅含一个数据元素，则R为空集；为空集；其他情况下的其他情况下的R存在二元关系：存在二元关系： root 唯一唯一 /关于根的说明关于根的说明 DjDk= /关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有15个个树与二叉树102. 若干术语若干术语即上层的那个结点即上层的

6、那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点ABCGEIDHFJMLK 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集棵不相交的树的集合合(例如删除例如删除A后的子树个数后的子

7、树个数)双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙结点各子树从左至右有序，不能互换（左为第一）结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。结点各子树可互换位置。树与二叉树112. 若干术语（续）若干术语（续）即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数（有几个直接后继就是几度（有几个直接后继就是几度，亦称，亦称“次数次数”）结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)ABCGEIDHFJMLK从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即

8、度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点（也称为内部结点）的结点（也称为内部结点）所有结点度中的最大值（所有结点度中的最大值（Max各结点的度各结点的度）指所有结点中最大的层数（指所有结点中最大的层数（Max各结点的层次各结点的层次）问：问：右上图中的结点数右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4树与二叉树123. 树的逻辑结构树的逻辑结构 ( (特点特点) )： 一对多（一对多（1:n1:n），有多个直接后继（如家谱），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，树、目录树等等），但只有一个根结点，且且子树之间互不相交子树之

9、间互不相交。 4. 树的存储结构树的存储结构 讨论讨论1：树是非线性结构，该怎样存储？树是非线性结构，该怎样存储？仍然有顺序存储、链式存储等方式。仍然有顺序存储、链式存储等方式。 树与二叉树13讨论讨论3：树的树的链式存储链式存储方案应该怎样制定？方案应该怎样制定？可规定为：可规定为：从上至下、从左至右从上至下、从左至右将树的结点依次存入内存。将树的结点依次存入内存。重大缺陷：复原困难（不能唯一复原就没有实用价值）。重大缺陷：复原困难（不能唯一复原就没有实用价值）。讨论讨论2：树的树的顺序存储顺序存储方案应该怎样制定？方案应该怎样制定？可用多重链表：可用多重链表：一个前趋指针，一个前趋指针，n

10、 n个后继指针。个后继指针。细节问题：细节问题：树中结点的结构类型样式该如何设计？树中结点的结构类型样式该如何设计？ 即应该设计成即应该设计成“等长等长”还是还是“不等长不等长”？缺点：缺点：等长结构太浪费（每个结点的度不一定相同）；等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。不等长结构太复杂（要定义好多种结构类型）。解决思路：解决思路：先研究最简单、最有规律的树，然后设法把先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。一般的树转化为简单树。树与二叉树145. 树的运算树的运算 要明确：要明确：1. 普通树（即多叉树）若不转化为二叉树，则

11、运普通树（即多叉树）若不转化为二叉树，则运算很难实现。算很难实现。2. 二叉树的运算仍然是插入、删除、修改、查找、二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在排序等，但这些操作必须建立在对树结点能够对树结点能够“遍历遍历”的基础上！的基础上！（遍历遍历指每个结点都被访问且仅访问一次，指每个结点都被访问且仅访问一次，不遗漏不重复）。不遗漏不重复）。本章重点：二叉树的表示和实现本章重点：二叉树的表示和实现树与二叉树156.2 6.2 二叉树二叉树为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “ “叉叉” ” 的树？的树？ 二叉树的结构最简单，规律性最强

12、；二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。可以证明，所有树都能转为唯一对应的二叉树，不失一般性。1. 二叉树的定义二叉树的定义2. 二叉树的性质二叉树的性质3. 二叉树的存储结构二叉树的存储结构（二叉树的运算（二叉树的运算见见6.3节节）树与二叉树16定义：定义：是是n（n0）个结点的有限集合，由一个根结点以及两）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为棵互不相交的、分别称为左子树和右子树左子树和右子树的二叉树组成的二叉树组成 。逻辑结构：逻辑结构： 一对二（一对二（1：2） 基本特征基本特征: 每个结点最多只有两棵子树（不存在

13、度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）；的结点）； 左子树和右子树次序不能颠倒（有序树）。左子树和右子树次序不能颠倒（有序树）。基本形态：基本形态： 5种种/2种种树与二叉树17二叉树的抽象数据类型定义二叉树的抽象数据类型定义（见教材（见教材P P121-122121-122）ADT BinaryTree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT BinaryTree若若D=，则，则R= ；若若D，则，则R= H；存在二元关系：；存在二元关系： root 唯一唯一 /关于根的说明关于根的说明 DjDk= /关于子树不相交的说明关于子树不相交的说明

14、/关于数据元素的说明关于数据元素的说明 /关于左子树和右子树的说明关于左子树和右子树的说明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有20个个树与二叉树18讨论讨论1 1：第：第i i层的结点数至多是多少？层的结点数至多是多少？ （利用二进制性质可轻松求出）（利用二进制性质可轻松求出） 性质性质1: 1: 在二叉树的第在二叉树的第i i层上至多有层上至多有个结点（个结点（i0i0）。）。性质性质2: 2: 深度为深度为k k的二叉树至多有的二叉树至多有个结点（个结点（k0k0）。）。2 2i-1i-1个个提问：第提问：第i i层上至少有层上至少有 个结点？个

15、结点？1 1讨论讨论2 2：深度为：深度为k k的二叉树，至多有多少个结点？的二叉树，至多有多少个结点？ （利用二进制性质可轻松求出）（利用二进制性质可轻松求出）2 2k k-1-1提问：深度为提问：深度为k k时至少有时至少有 个结点？个结点？k k树与二叉树19讨论讨论3 3：二叉树的叶子数和度为：二叉树的叶子数和度为2 2的结点数之间有关系吗？的结点数之间有关系吗？性质性质3: 3: 对于任何一棵二叉树，若对于任何一棵二叉树，若2 2度的结点数有度的结点数有n n2 2个，个，则叶子数（则叶子数（n n0 0）必定为必定为n n2 21 1 （即（即n0=n2+1）二叉树中全部结点数二叉

16、树中全部结点数nn0+n1+n2( (叶子数叶子数1 1度结点数度结点数2 2度结点数度结点数) )二叉树中全部结点数二叉树中全部结点数nB+1 ( ( 总分支数根结点总分支数根结点 ) ) （除根结点外，每个结点必有一个直接前趋，即一个分支）（除根结点外，每个结点必有一个直接前趋，即一个分支）总分支数总分支数B= n1+2n2 (1(1度结点必有度结点必有1 1个直接后继，个直接后继，2 2度结点必有度结点必有2 2个个) )n0+n1+n2= n1+2n2 +1, 即即n0=n2+1实际意义：实际意义：叶子数叶子数2 2度结点数度结点数1 1ABCGEIDHFJ树与二叉树20对于两种特殊形

17、式的二叉树（对于两种特殊形式的二叉树（满二叉树和完全二叉树满二叉树和完全二叉树），），还特别具备以下还特别具备以下2 2个性质：个性质：性质性质4: 4: 具有具有n n个结点的完全二叉树的深度必为个结点的完全二叉树的深度必为loglog2 2nn1 1性质性质5: 5: 对完全二叉树，若从上至下、从左至右编号，对完全二叉树，若从上至下、从左至右编号，则编号为则编号为i 的结点，其左孩子编号必为的结点，其左孩子编号必为2i，其右孩子编号，其右孩子编号必为必为2i1；其双亲的编号必为；其双亲的编号必为i/2（i1 时为根时为根, ,除外除外）。）。 证明：根据性质证明：根据性质2 2，深度为，深

18、度为k k的二叉树最多只有的二叉树最多只有2 2k k-1-1个结点，且完全二叉树个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数的定义是与同深度的满二叉树前面编号相同，即它的总结点数n n位于位于k k层和层和k-1k-1层满二叉树容量之间，即层满二叉树容量之间，即 2 2k-1k-1-1n2-1n2k k-1 -1 或或2 2k-1k-1n n 2 2k k三边同时取对数，于是有：三边同时取对数，于是有：k-1logk-1log2 2nk n1)f=n*fact(n-1); else f=1; return(f); 树与二叉树34先序遍历算法先序遍历算法DLR(

19、liuyu *root )if (root !=NULL) /非空二叉树非空二叉树 printf(“%d”,root-data); /访问访问D DDLR(root-lchild); /递归遍历左子树递归遍历左子树DLR(root-rchild); /递归遍历右子树递归遍历右子树 return(0); 中序遍历算法中序遍历算法LDR(x*root)if(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rchild); return(0);后序遍历算法后序遍历算法LRD (x*root)if(root !=NULL)

20、 LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); return(0);结点数据类型自定义结点数据类型自定义typedef struct liuyuint data; struct liuyu *lchild,*rchild； liuyu;liuyu *root; 树与二叉树35对遍历的分析：对遍历的分析：1. 从前面的三种遍历算法可以知道：如果将从前面的三种遍历算法可以知道：如果将print语句抹去，语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的

21、遍历算法的访问路径是相同的，只是访问结点的时机不同访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径从虚线的出发点到终点的路径上，每个结点经过上，每个结点经过3次次。AFEDCBG第第1次经过时访问先序遍历次经过时访问先序遍历第第2次经过时访问中序遍历次经过时访问中序遍历第第3次经过时访问后序遍历次经过时访问后序遍历2. 2. 二叉树遍历的时间效率和空间效率二叉树遍历的时间效率和空间效率时间效率时间效率: : /每个结点只访问一次每个结点只访问一次空间效率空间效率: : /栈占用的最大辅助空间栈占用的最大辅助空间（精确值：树深为（精确值：树深为k k的递归遍历需要的递归遍历需

22、要k+1k+1个辅助单元！）个辅助单元！）树与二叉树36例：例：【严题集【严题集6.42】编写递归算法，计算二叉编写递归算法，计算二叉树中叶子结点的数目。树中叶子结点的数目。 思路：思路：输出叶子结点比较简单，用任何一种遍历算法，凡输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。是左右指针均空者，则为叶子，将其统计并打印出来。 DLR(liuyu *root) /采用中序遍历的递归算法采用中序遍历的递归算法 if ( root!=NULL ) /非空二叉树条件，还可写成非空二叉树条件，还可写成if(root)if(root) if(!root-lch

23、ild&!root-rchild) /是叶子结点则统计并打印是叶子结点则统计并打印 sum+; printf(%dn,root-data); DLR(root-lchild); /递归遍历左子树，直到叶子处；递归遍历左子树，直到叶子处； DLR(root-rchild); /递归遍历右子树，直到叶子处；递归遍历右子树，直到叶子处； return(0); 树与二叉树37注：要实现遍历运算必须先把二叉树存入机内。注：要实现遍历运算必须先把二叉树存入机内。思路：思路：利用利用前序前序遍历来建树遍历来建树 （结点值陆续从键盘输入，用（结点值陆续从键盘输入，用DLR为宜为宜）Bintree create

24、BTpre( ) Bintree T; char ch;scanf(“%c”,&ch);if(ch=)T=NULL; elseT=( Bintree )malloc(sizeof(BinTNode);T-data=ch;T-lchild=createBTpre();T-rchild=createBTpre(); return T;怎样建树？见教材怎样建树？见教材P131P131程序。程序。树与二叉树38习题讨论：习题讨论： 算法思路：算法思路：只查各结点后继链表指针，若左只查各结点后继链表指针，若左( (右右) )孩子的左孩子的左( (右右) )指针非空，则层次数加指针非空，则层次数加1 1；

25、否则函数返回。；否则函数返回。技巧：技巧：递归时应当递归时应当从叶子开始向上计数，层深者保留。从叶子开始向上计数，层深者保留。否则否则不易确定层数。不易确定层数。 算法思路：算法思路：既然要求从上到下，从左到右，则既然要求从上到下，从左到右，则利用队列利用队列存放存放各子树结点的指针是个好办法，而不必拘泥于递归算法。各子树结点的指针是个好办法，而不必拘泥于递归算法。技巧：技巧：当根结点入队后，令其左、右孩子结点入队，而左孩当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，子出队时又令它的左右孩子结点入队，由此便可产生按由此便可产生按层次输出的效果。层次输出的效果。

26、 A B CD E树与二叉树39算法思路：算法思路：若不用递归，则要实现二叉树遍历的若不用递归，则要实现二叉树遍历的“嵌套嵌套”规规则，必用堆栈。可直接用则，必用堆栈。可直接用whilewhile语句和语句和push/poppush/pop操作。操作。参见教参见教材材P130-131P130-131程序。程序。 算法思路：算法思路：完全二叉树的特点是：没有左子树空而右子树单完全二叉树的特点是：没有左子树空而右子树单独存在的情况独存在的情况( (前前k-1k-1层都是满的，且第层都是满的，且第k k层左边也满）层左边也满）。技巧技巧: :按层序遍历方式，先把所有结点按层序遍历方式，先把所有结点（

27、不管当前结点是否有（不管当前结点是否有左右孩子）左右孩子）都入队列都入队列. .若为完全二叉树若为完全二叉树, ,则层序遍历时得到的则层序遍历时得到的肯定是一个连续的不包含空指针的序列肯定是一个连续的不包含空指针的序列. .如果序列中出现了空如果序列中出现了空指针，则说明不是完全二叉树。指针，则说明不是完全二叉树。树与二叉树40【严题集【严题集6.31】 证明：由一棵二叉树的先序序列和中序证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。序列可唯一确定这棵二叉树。 例：例：已知一棵二叉树的已知一棵二叉树的中序序列中序序列和和后序序列后序序列分别是分别是BDCEAFHG 和和 DECB

28、HGFA，请画出这棵二叉树。，请画出这棵二叉树。分析：分析：由后序遍历特征，根结点必在后序序列尾部由后序遍历特征，根结点必在后序序列尾部（即（即A A）；由中序遍历特征，根结点必在其中间，而且其左部必全部是由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙左子树子孙（即（即BDCEBDCE），其右部必全部是右子树子孙，其右部必全部是右子树子孙（即（即FHGFHG）；继而，根据后序中的继而，根据后序中的DECBDECB子树可确定子树可确定B B为为A A的左孩子，根据的左孩子，根据HGFHGF子串可确定子串可确定F F为为A A的右孩子；以此类推。的右孩子；以此类推。树与二叉树41中

29、序遍历：中序遍历：B D C E A F H G后序遍历：后序遍历：D E C B H G F A（B D C E）（ F H G）ABF （D C E） （ H G）CD EGHABBFF树与二叉树42问：问：用二叉链表法（用二叉链表法（l_child, r_child）存储包含）存储包含n个结点的个结点的二叉树，结点的指针区域中会有多少个空指针？二叉树，结点的指针区域中会有多少个空指针？分析：分析：用二叉链表存储包含用二叉链表存储包含n n个结点的二叉树，结点必有个结点的二叉树，结点必有2n个链域个链域（见二叉链表数据类型说明）（见二叉链表数据类型说明）。除根结点外，二叉树中每一个结点除根

30、结点外，二叉树中每一个结点有且仅有一个双亲有且仅有一个双亲（直接前驱），所以只会有（直接前驱），所以只会有n n1 1个结点的链域存放指针，指个结点的链域存放指针，指向非空子女结点（即直接后继）。向非空子女结点（即直接后继）。思考：思考：二叉链表空间效率这么低，能否利用这些空闲区存放二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？有用的信息或线索？我们可以用它来存放当前结点的直接前驱和后继等线索，我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。以加快查找速度。所以，所以， 空指针数目空指针数目2n(n-1)=n+1个个。n+1树与二叉树43二、线索二叉树线索二

31、叉树（Threaded Binary Tree）普通二叉树只能找到结点的左右孩子信息，普通二叉树只能找到结点的左右孩子信息，而该结点而该结点的直接前驱和直接后继只能在遍历过程中获得。的直接前驱和直接后继只能在遍历过程中获得。若将若将遍历后遍历后对应的有关前驱和后继对应的有关前驱和后继预存预存起来，则从起来，则从第第一个结点一个结点开始就能很快开始就能很快“顺藤摸瓜顺藤摸瓜”而遍历整个树了。而遍历整个树了。两种解决方法：两种解决方法：增加两个域：增加两个域：fwd和和bwd；存放前驱指针存放前驱指针存放后继指针存放后继指针如何预存这类信息？如何预存这类信息？例如中序遍历结果：例如中序遍历结果：B

32、 D C E A F H GB D C E A F H G，实际上，实际上已将二叉已将二叉树转为树转为线性排列线性排列，显然具有唯一前驱和唯一后继。，显然具有唯一前驱和唯一后继。1. 1. 定义定义 2. 2. 生成生成 3. 3. 遍历遍历利用空链域（利用空链域（n+1个空链域）个空链域）树与二叉树44规定：规定：1）若结点有左子树，则）若结点有左子树，则lchild指向其左孩子；指向其左孩子； 否则，否则， lchild指向其直接前驱指向其直接前驱(即线索即线索)；2）若结点有右子树，则）若结点有右子树，则rchild指向其右孩子；指向其右孩子； 否则，否则， rchild指向其直接后继指

33、向其直接后继(即线索即线索) 。为区别两种不同情况，特增加两个标志域（各为区别两种不同情况，特增加两个标志域（各1bit)lchilddatarchild约定约定:当当Tag域为域为0时时,表示表示正常正常情况情况;当当Tag域为域为1时时,表示表示线索线索情况情况.右孩子或后继右孩子或后继左孩子或前驱左孩子或前驱LTagRTag树与二叉树45附：有关线索二叉树的几个术语：附：有关线索二叉树的几个术语： 线索链表：线索链表：用用含含Tag的结点样式所构成的二叉链表的结点样式所构成的二叉链表 线线 索：索：指向结点前驱和后继的指针指向结点前驱和后继的指针线索二叉树：线索二叉树：加上线索的二叉树加

34、上线索的二叉树 线线 索索 化：化：对二叉树以对二叉树以某种次序遍历某种次序遍历使其变为线索二使其变为线索二叉树的过程叉树的过程讨论：讨论：增加了前驱和后继等线索有什么好处？增加了前驱和后继等线索有什么好处？能方便找出当前结点的前驱和后继，不用能方便找出当前结点的前驱和后继，不用堆栈也能遍历整个树。堆栈也能遍历整个树。树与二叉树46data AGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例：例：某某先序遍历先序遍历结果如下表所示，请画出对应的结果如下表所示，请画出对应的二叉树。二叉树。（多带了两个标志！）（多带了两个标志！）树与二叉树472.

35、2. 线索二叉树的生成线索二叉树的生成线索化过程就是线索化过程就是在遍历过程中修改空指针在遍历过程中修改空指针的过程：的过程：将空的将空的l lchildchild改为结点的直接前驱；改为结点的直接前驱；将空的将空的r rchildchild改为结点的直接后继。改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为非空指针呢？仍然指向孩子结点（称为“正常情况正常情况”）树与二叉树48ABCGEIDHFroot悬空？悬空？悬空？悬空？解：解：该二叉树中序遍历结果为该二叉树中序遍历结果为: : H, D, I, B, E, A, F, C, G所以添加线索应当按如下路径进行：所以添加线索应当按如下

36、路径进行：为避免悬空为避免悬空态，应增设态，应增设一个头结点一个头结点例例1 1：画出以下二叉树对应的画出以下二叉树对应的中序中序线索二叉树。线索二叉树。树与二叉树4900A00C00B11E11F11G00D11I11H注：此图中序遍历结果为注：此图中序遍历结果为: : H, D, I, B, E, A, F, C, G0-root0对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：树与二叉树50例例2 2：【 2000年计算机系考研题】年计算机系考研题】给定如图所示给定如图所示二叉树二叉树T T，请画出与其对应的中序线索二叉树。，请画出与其对应的中序线索二叉树。

37、2825405560330854解解: :因为中序遍历序列是：因为中序遍历序列是：5555 40 25 60 40 25 60 2828 08 33 08 33 5454对应线索树应当按此规律连线，即对应线索树应当按此规律连线，即在原二叉树中添加虚线。在原二叉树中添加虚线。NILNILNILNIL树与二叉树51线索二叉树的生成算法线索二叉树的生成算法（算法算法6.6, 见教材见教材P134）目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后 继。继。注解：为方便添加结点的前驱或后继，需要设置两个指针：注解：为方便添加结点的前驱或后继，需

38、要设置两个指针： p指针指针当前结点之指针；当前结点之指针； pre指针指针前驱结点之指针。前驱结点之指针。技巧：技巧：当结点当结点p的左的左/右域为空右域为空时，只改写它的左域（装入前驱时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。，而其右域（后继）留给下一结点来填写。 或者说，当前结点的指针或者说，当前结点的指针p应当送到前驱结点的空右域中。应当送到前驱结点的空右域中。若若p-lchildNULL, ,则则p-Ltag=1;p-Ltag=1;p-lp-lchildchildpre; ; /p/p的前驱结点指针的前驱结点指针pre存入左空域存入左空域若若pre-r

39、childNULL, 则则pre-Rtagpre-Rtag1;pre-rchild=p; /p存入其前驱结点存入其前驱结点pre的右的右空域空域树与二叉树523. 3. 线索二叉树的遍历线索二叉树的遍历理论上，只要找到序列中的理论上，只要找到序列中的第一个结点第一个结点，然后，然后依次访依次访问结点的后继问结点的后继直到后继为空时结束。直到后继为空时结束。在线索化二叉树中，并不是每个结点都能直接找到其在线索化二叉树中，并不是每个结点都能直接找到其后继的，后继的，当标志为当标志为0 0时，时，R_child=R_child=右孩子地址指针，并非后继！右孩子地址指针，并非后继！需要通过一定运算才能

40、找到它的后继。需要通过一定运算才能找到它的后继。以以中序线索二叉树中序线索二叉树为例：为例：对叶子结点（对叶子结点（RTag=1），直接后继指针就在其），直接后继指针就在其rchild域内；域内；对其他结点（对其他结点（RTag=0），直接后继是其），直接后继是其右子树最左下的结点右子树最左下的结点；（因为中序遍历规则是（因为中序遍历规则是LDR，）树与二叉树53程序注解程序注解 (非递归，且不用栈非递归，且不用栈）：）：P=T-lchild; /从头结点进入到根结点；从头结点进入到根结点；while( p!=T) while(p-LTag=link)p=p-lchild; /先找到中序遍历起

41、点先找到中序遍历起点 if(!visit(p-data) return ERROR; /若起点值为空则出错告警若起点值为空则出错告警 while(p-RTag=Thread ) p=p-rchild; Visit(p-data); /若有后继标志，则直接提取若有后继标志，则直接提取p-rchild中线索并中线索并访问后继结点；访问后继结点；p=p-rchild; /当前结点右域不空当前结点右域不空或或已经找好了后继已经找好了后继，则一律从，则一律从结点的右子树开始重复结点的右子树开始重复 的全部过程。的全部过程。Return OK;线索二叉树的线索二叉树的中序中序遍历算法遍历算法（算法算法6.

42、5, 参见教材参见教材P134）LTag=0RTag=1树与二叉树54算法流程：算法流程：return OK;p=T-lchild;p!=Tp-LTag=0p=p-lchild;vist(p-data);p-LTag=1&p-rchild!=Tp=p-rchild;visit(p-data);p=p-rchild;YNYNYN演演示示程程序序树与二叉树55提前介绍：二叉树的应用提前介绍：二叉树的应用平衡树平衡树排序树排序树字典树字典树判定树判定树带权树带权树最优树最优树特点：左右子树深度差特点：左右子树深度差 1特点：特点：“左小右大左小右大”（见实验二的方案（见实验二的方案1）由字符串构成的

43、二叉树排序树由字符串构成的二叉树排序树例如，例如，12个球只称个球只称3次分出轻重次分出轻重特点：路径长度带权值特点：路径长度带权值 带权路径长度最短的树，又称带权路径长度最短的树，又称 Huffman树，用途之一是通信中的压缩编码。树，用途之一是通信中的压缩编码。树与二叉树566.4 树和森林1. 树和森林与二叉树的转换树和森林与二叉树的转换2. 树和森林的存储方式树和森林的存储方式3. 树和森林的遍历树和森林的遍历树与二叉树571. 树和森林与二叉树的转换树和森林与二叉树的转换转换步骤：转换步骤：step1: step1: 将树中同一结点的兄弟相连将树中同一结点的兄弟相连; ;step2:

44、 step2: 保留结点的最左孩子连线，删除其它孩保留结点的最左孩子连线，删除其它孩子连线；子连线；step3: step3: 将同一孩子的连线绕左孩子旋转将同一孩子的连线绕左孩子旋转4545度角。度角。加线加线抹线抹线旋转旋转讨论讨论1 1：树如何转为二叉树？：树如何转为二叉树？树与二叉树58方法：方法：加加线线抹线抹线旋转旋转 abeidfhgc树转二叉树举例：树转二叉树举例：abeidfhgc兄弟相连兄弟相连长兄为父长兄为父孩子靠左孩子靠左树与二叉树59讨论讨论2 2：二叉树怎样还原为树？：二叉树怎样还原为树？abeidfhgc要点：把所有右孩子变为兄弟！要点：把所有右孩子变为兄弟！ a

45、beidfhgc树与二叉树60法一：法一： 各森林先各自转为二叉树；各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。依次连到前一个二叉树的右子树上。讨论讨论3 3：森林如何转为二叉树？：森林如何转为二叉树？法二：法二：森林直接变兄弟，再转为二叉树森林直接变兄弟，再转为二叉树（参见教材（参见教材P138P138图图6.176.17，两种方法都有转换示意图），两种方法都有转换示意图）即即F=TF=T1 1, T, T2 2, ,T, ,Tm m B=root, LB, RB B=root, LB, RB树与二叉树61ABCDEFGHJIABCDEFGHJIBCDEFGHJI森林转二叉树举

46、例：森林转二叉树举例：（法二）（法二）兄弟相连兄弟相连 长兄为父长兄为父孩子靠左孩子靠左 头根为根头根为根 树与二叉树62讨论讨论4 4：二叉树如何还原为森林？：二叉树如何还原为森林？要点：要点：把最右边的子树变为森林，其余右子树变为兄弟把最右边的子树变为森林，其余右子树变为兄弟 ABCDEFGHJIABCDEFGHJIEFABCDGHJI即即B=root, LB, RB F=TB=root, LB, RB F=T1 1, T, T2 2, ,T, ,Tm m 树与二叉树632. 2. 树和森林的存储方式树和森林的存储方式树有三种常用存储方式：树有三种常用存储方式：双亲表示法双亲表示法 孩子表

47、示法孩子表示法 孩子兄弟表示法孩子兄弟表示法 1 1、用双亲表示法来存储、用双亲表示法来存储思路：思路：用一组用一组连续空间连续空间来存储树的结点，同时在每个来存储树的结点，同时在每个结点中结点中附设一个指示器附设一个指示器，指示其双亲结点在链表中的，指示其双亲结点在链表中的位置。位置。parentsdata结点结构结点结构dataparents1树结构树结构 23n树与二叉树64缺点：求结点的孩子时需要遍历整个结构。缺点：求结点的孩子时需要遍历整个结构。01234567812233ABCDEFGHI-1001例例1: 双亲表示法双亲表示法树与二叉树65思路：将每个结点的孩子排列起来，形成一个

48、带表头思路：将每个结点的孩子排列起来，形成一个带表头（装父结点）的线性表（装父结点）的线性表（n n个结点要设立个结点要设立n n个链表）；个链表）；再将再将n n个表头用数组存放起来，这样就形成一个混合个表头用数组存放起来，这样就形成一个混合结构。结构。例如例如：abecdfhgdefghgfedcbah123456782 2、用孩子表示法来存储、用孩子表示法来存储bc树与二叉树66思路：思路：用二叉链表来表示树，但链表中的两个用二叉链表来表示树，但链表中的两个指针域含义不同。指针域含义不同。左指针指向该结点的第一个孩子；左指针指向该结点的第一个孩子；右指针指向该结点的下一个兄弟结点。右指针

49、指向该结点的下一个兄弟结点。nextsiblingdatafirstchild3 3、用孩子兄弟表示法来存储、用孩子兄弟表示法来存储指向左孩子指向左孩子指向右兄弟指向右兄弟树与二叉树67abecdfhgbacedfgh问：问：树树二叉树的二叉树的“连线连线抹线抹线旋转旋转” ” 如如何由计算机自动实现？何由计算机自动实现？答：答：用用“左孩子右兄弟左孩子右兄弟”表示法来存储即可。表示法来存储即可。 例如例如：树与二叉树68 先序遍历先序遍历F若森林为空，返回；若森林为空，返回；F访问森林中第一棵树的根结点；访问森林中第一棵树的根结点；F先序遍历第一棵树中根结点的子树森林；先序遍历第一棵树中根结

50、点的子树森林；F先序遍历除去第一棵树之后剩余的树构成的森林。先序遍历除去第一棵树之后剩余的树构成的森林。 中序遍历中序遍历F若森林为空，返回；若森林为空，返回；F中序遍历森林中第一棵树的根结点的子树森林；中序遍历森林中第一棵树的根结点的子树森林；F访问第一棵树的根结点；访问第一棵树的根结点；F中序遍历除去第一棵树之后剩余的树构成的森林。中序遍历除去第一棵树之后剩余的树构成的森林。森林的遍历森林的遍历ABCDEFGHJI树与二叉树69路路 径径：路径长度路径长度：树的路径长度树的路径长度：带权路径长度带权路径长度：树的带权路径长度树的带权路径长度：霍霍 夫夫 曼曼 树树：6.5 Huffman6

51、.5 Huffman树及其应用树及其应用一、最优二叉树（一、最优二叉树（霍夫曼霍夫曼树）树）由一结点到另一结点间的分支所构成由一结点到另一结点间的分支所构成路径上的分支数目路径上的分支数目从树根到从树根到每一结点每一结点的路径长度之和。的路径长度之和。结点到根的路径长度与结点上权的乘积结点到根的路径长度与结点上权的乘积预备知识：若干术语预备知识：若干术语debacf g树中所有树中所有叶子结点叶子结点的带权路径长度之和的带权路径长度之和带权路径长度最小的树。带权路径长度最小的树。aeae的路径长度的路径长度树长度树长度2 21010树与二叉树70HuffmanHuffman树简介：树简介：树的

52、带权路径长度如何计算？树的带权路径长度如何计算？WPLWPL = = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)WPL=36WPL=46WPL= 35哈夫曼树则是：哈夫曼树则是：WPL WPL 最小的树。最小的树。Huffman树树Weighted Path LengthWeighted Path Length树与二叉树71构造霍夫曼树的基本思想：构造霍夫曼树的基本思想：构造构造HuffmanHuffman树的步骤（即树的步骤（即HuffmanHuffman算法）：算法）：树与二叉树72设有设有4 4个字符个字符d,i,a,n

53、d,i,a,n，出现的频度分别为，出现的频度分别为7,5,2, 7,5,2, 4 4，怎样编码才能使它们组成的报文在网络中传得最快？，怎样编码才能使它们组成的报文在网络中传得最快？法法1 1：等长编码等长编码。例如用二进制编码来实现。例如用二进制编码来实现。 取取 d=d=0000，i=i=0101，a=a=1010，n=n=1111怎样实现怎样实现HuffmanHuffman编码？编码？法法2 2：不等长编码不等长编码，例如用哈夫曼编码来实现。，例如用哈夫曼编码来实现。 取取 d=d=0 0; i=; i=1010, a=, a=110110, n=, n=111111最快的编码是哪个？最快

54、的编码是哪个？是非等长的是非等长的HuffmanHuffman码！码！先要构造先要构造HuffmanHuffman树！树！树与二叉树73操作要点操作要点1 1：对权值的合并、删除与替换对权值的合并、删除与替换在权值集合在权值集合7,5,2,47,5,2,4中，总是合并中，总是合并当前值最小当前值最小的两个权的两个权构造构造HuffmanHuffman树的步骤：树的步骤：注：方框表示外结点（叶子，字符对应的权值），注：方框表示外结点（叶子，字符对应的权值）， 圆框表示内结点（合并后的权值）。圆框表示内结点（合并后的权值）。树与二叉树74操作要点操作要点2 2：按左按左0 0右右1 1对对Huff

55、manHuffman树的所有分支编号！树的所有分支编号！d da ai in n1 11 11 10 00 00 0HuffmanHuffman编码结果：编码结果：d=d=0 0, i=, i=1010, a=, a=110110, n=, n=111111WPL=1bitWPL=1bit7 72bit2bit5+3bit(2+4)=5+3bit(2+4)=3535特点：每一码都不是另一码的前缀，绝不会错译特点：每一码都不是另一码的前缀，绝不会错译! ! 称为前缀码称为前缀码HuffmanHuffman树树 与与 HuffmanHuffman编码编码 挂钩挂钩树与二叉树75例例2 2（严题集（

56、严题集6.266.26）：假设用于通信的电文仅由假设用于通信的电文仅由8 8个字母个字母 a, a, b, c, d, e, f, g, hb, c, d, e, f, g, h 构成，它们在电文中出现的概率分别构成，它们在电文中出现的概率分别为为 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10，试为这试为这8 8个字母设计哈夫曼编码。个字母设计哈夫曼编码。如果用如果用0 07 7的二进制编码方案的二进制编码方案又如何？又如何？霍夫曼霍夫曼编码的基本思想是

57、：概率大的字符用短码，概率小的用编码的基本思想是：概率大的字符用短码，概率小的用长码。由于长码。由于霍夫曼树的霍夫曼树的WPLWPL最小，说明编码所需要的比特数最最小，说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。少。这种编码已广泛应用于网络通信中。解：解：先将概率放大先将概率放大100100倍，以方便构造哈夫曼树。倍，以方便构造哈夫曼树。权值集合权值集合 w=7, 19, 2, 6, 32, 3, 21, 10w=7, 19, 2, 6, 32, 3, 21, 10，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。

58、树与二叉树76w4=19, 21, w4=19, 21, 28,28, 32 32为清晰起见，重新排序为为清晰起见，重新排序为: :w=2, 3, 6, 7, 10, 19, 21, 32w=2, 3, 6, 7, 10, 19, 21, 322 23 35 56 6w1=w1=5,5, 6, 7, 10, 19, 21, 32 6, 7, 10, 19, 21, 32w2=7, 10, w2=7, 10, 11,11, 19, 21, 32 19, 21, 32w3=w3=11, 17,11, 17, 19, 21, 32 19, 21, 32111110107 717172828212119194040w5=w5=28,28,32,32,4040 32326060w6=w6=40,6040,60 w7=w7=100100 100100b bc ca ad de eg gf fh h哈夫曼树哈