ch6 树和二叉树

1、1第第6章章 树和二叉树树和二叉树（ Tree & Binary Tree ）6.1 树的基本概念树的基本概念6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 赫夫曼树及其应用赫夫曼树及其应用特点：特点：非线性结构，一个直接前驱，但可能有多个非线性结构，一个直接前驱，但可能有多个直接后继直接后继（1：n）26.1 树的基本概念1. 树的定义和表示树的定义和表示2. 树的若干术语树的若干术语3. 树的逻辑结构树的逻辑结构4. 树的存储结构树的存储结构5. 树的运算树的运算31. 树的定义树的定义注注1：过去许多书籍中都定义树为过去许多书籍中都

2、定义树为n1，曾经有，曾经有“空树不是空树不是 树树”的说法，但现在树的定义已修改。的说法，但现在树的定义已修改。注注2：树的定义具有树的定义具有递归性递归性，即树中还有树。，即树中还有树。由由0个或多个个或多个(n0)结点组成的有限集合结点组成的有限集合T T，有且仅，有且仅有有一个结点称为根一个结点称为根（root），），当当n1时，其余的结点分时，其余的结点分为为m(m0)个个互不相交互不相交的有限集合的有限集合T1,T2，Tm。每。每个集合本身又是棵树，被称作这个根的个集合本身又是棵树，被称作这个根的子树子树 。6.1 树的基本概念4树的表示法有几种：树的表示法有几种：图形表示法图形表

3、示法嵌套集合表示法嵌套集合表示法广义表表示法广义表表示法目录表示法目录表示法左孩子右兄弟表示法左孩子右兄弟表示法这些表示法的示意图这些表示法的示意图参见教材参见教材P120树的抽象数据类型定义树的抽象数据类型定义参参见教材见教材P118-1196.1 树的基本概念5图形表示法：图形表示法：教师教师学生学生其他人员其他人员20082008级级20092009级级 20102010级级20112011级级河南大学河南大学数学学院数学学院计算机学院计算机学院物理学院物理学院叶子叶子根根子树子树6广义表表示法广义表表示法( A ( B ( E ( K, L ), F ), C ( G ), D ( H

4、 ( M ), I, J ) ) 根作为根作为由子树森林组成的由子树森林组成的表的名字写在表的左边表的名字写在表的左边datalink 1 link 2.link n麻烦问题：应当开设多少个链域麻烦问题：应当开设多少个链域?ABCGEIDHFJMLK6.1 树的基本概念1. 树的定义树的定义7左孩子右兄弟表示法左孩子右兄弟表示法数据数据左孩子左孩子 右兄弟右兄弟ABCGEIDHFJMLK6.1 树的基本概念1. 树的定义树的定义8数据对象数据对象 D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 若若D为空集，则称为空树；为空集，则称为空树； 否则否则: (1) 在在D中

5、存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root, (2) 当当n1时，其余结点可分为时，其余结点可分为m (m0)个互不相交个互不相交 的有限集的有限集T1, T2, , Tm, 其中每一棵子集本身又其中每一棵子集本身又 是一棵符合本定义的树，称为根是一棵符合本定义的树，称为根root的子树。的子树。 数据关系数据关系 R： 树的抽象数据类型定义树的抽象数据类型定义（见教材（见教材P118-119）6.1 树的基本概念1. 树的定义树的定义9 基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类6.1 树的基本概念10Root(T) / 求树的根结点求树的根结

6、点 查找类：查找类：Value(T, cur_e) / 求当前结点的元素值求当前结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(T, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树判定树是否为空树 TreeDepth(T) / 求树的深度求树的深度TraverseTree( T, Visit() ) / 遍历遍历6.1 树的基本概念11InitTree(&T) / 初始化置空树初始化置空

7、树 插入类：插入类：CreateTree(&T, definition) / 按定义构造树按定义构造树Assign(T, cur_e, value) / 给当前结点赋值给当前结点赋值InsertChild(&T, &p, i, c) / 将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树6.1 树的基本概念12 ClearTree(&T) / 将树清空将树清空 删除类：删除类：DestroyTree(&T) / 销毁树的结构销毁树的结构DeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i棵子树棵子树6.1 树的基本概念132. 若干术语若干术语即上

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

9、删除例如删除A后的子树个数后的子树个数)双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙子树从左至右有序，不能互换（左为第一）。子树从左至右有序，不能互换（左为第一）。有确定的根，树根和子树根之间为有向关系。有确定的根，树根和子树根之间为有向关系。结点各子树可互换位置。结点各子树可互换位置。142. 若干术语（续）若干术语（续）即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数（有几个直接后继就是几度，（有几个直接后继就是几度，亦称亦称“次数次数”）结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)ABCGEI

10、DHFJMLK从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点（也称为内部结点）的结点（也称为内部结点）所有结点度中的最大值（所有结点度中的最大值（Max各结点的度各结点的度）指所有结点中最大的层数（指所有结点中最大的层数（Max各结点的层次各结点的层次）问：问：右上图中的结点数右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4153. 树的逻辑结构树的逻辑结构 ( (特点特点) )： 一对多（一对多（1:n1:n），有多个直接后继（如家谱），有多个直接后继（如家谱树、目录树等等

11、），但只有一个根结点，树、目录树等等），但只有一个根结点，且且子树之间互不相交子树之间互不相交。 4. 树的存储结构树的存储结构 讨论讨论1：树是非线性结构，该怎样存储？树是非线性结构，该怎样存储？仍然有顺序存储、链式存储等方式。仍然有顺序存储、链式存储等方式。 16讨论讨论3：树的树的链式存储链式存储方案应该怎样制定？方案应该怎样制定？可规定为：可规定为：从上至下、从左至右从上至下、从左至右将树的结点依次存入内存。将树的结点依次存入内存。重大缺陷：重大缺陷：复原困难（不能唯一复原就没有实用价值）。复原困难（不能唯一复原就没有实用价值）。讨论讨论2：树的树的顺序存储顺序存储方案应该怎样制定？方

12、案应该怎样制定？可用多重链表：可用多重链表：一个前趋指针，一个前趋指针，n n个后继指针。个后继指针。细节问题：细节问题：树中结点的结构类型样式该如何设计？树中结点的结构类型样式该如何设计？ 即应该设计成即应该设计成“等长等长”还是还是“不等长不等长”？缺点：缺点：等长结构太浪费（每个结点的度不一定相同）；等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。不等长结构太复杂（要定义好多种结构类型）。解决思路：解决思路：先研究最简单、最有规律的树，然后设法把先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。一般的树转化为简单树。175. 树的运算树的运

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

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

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

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

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

18、+1）二叉树中全部结点数二叉树中全部结点数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

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

20、2 2，深度为，深度为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 ndata); /访问访问D DLR(root-lchild); /递归遍历左子树递归遍历左子树 DLR(r

21、oot-rchild); /递归遍历右子树递归遍历右子树 return(0); 二叉树结点数据类型定义：二叉树结点数据类型定义：typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;则三种遍历算法可写出则三种遍历算法可写出: :2. 二叉树二叉树遍历算法的递归实现遍历算法的递归实现 43中序遍历算法中序遍历算法 LDR (BiTNode *root) if (root !=NULL) LDR(root-lchild); printf (“%d”,root-data); L

22、DR(root-rchild); return(0); 后序遍历算法后序遍历算法 LRD (BiTNode *root) if (root !=NULL) LRD(root-lchild); LRD(root-rchild); printf (“%d”,root-data); return(0); 2. 二叉树二叉树遍历算法的递归实现遍历算法的递归实现 44对遍历的分析：对遍历的分析：1. 从前面的三种遍历算法可以知道：从前面的三种遍历算法可以知道：如果将如果将print语句抹去，语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种从递归的角度看，这三种算法是完全相同的，或者说这三种

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

24、历需要k+1k+1个辅助单元！）个辅助单元！）45算法思路：算法思路：若不用递归，则要实现二叉树遍历的若不用递归，则要实现二叉树遍历的“嵌套嵌套”规则，规则， 必用堆栈。必用堆栈。参见教材参见教材P130-131程序。程序。Status InOrderTraverse ( Bitree T, Status (* Visit) (TElemType e) ) InitStack( S ); Push( S, T ); / 根指针进栈根指针进栈 while ( !StackEmpty(S) ) while( GetTop(S, p) & p) Push( S, p-lchild ); / 向左走到

25、尽头向左走到尽头 Pop( S, p ); / 空指针退栈空指针退栈 if ( !StackEmpty(S) ) / 访问结点访问结点, ,向右一步向右一步 Pop( S, p ); if (!Visit ( p-data ) ) return ERROR; Push ( S, p-rchild ); / 将右儿子入栈，则下次循环时打印右儿子将右儿子入栈，则下次循环时打印右儿子 / if /while return OK; / InOrderTraverse 3. 二叉树二叉树遍历算法的非递归实现遍历算法的非递归实现 46Status InorderTraverse ( BiTree T, S

26、tatus( *Visit) (TElemType e) InitStack( S ); p=T; while ( p | !StackEmpty(S) ) / 栈不空或树不空栈不空或树不空 if ( p ) Push(S,p); p= p-lchild; / 根指针进栈根指针进栈, ,遍历左子树遍历左子树 else / 根指针退栈根指针退栈, ,访问根结点访问根结点, ,遍历右子树遍历右子树 Pop( S,p); if ( !Visit( p-data) ) return ERROR; p = p-rchild; / else / while return OK; / InorderTrav

27、erse 47例例5 判断二叉树是否为完全二叉树判断二叉树是否为完全二叉树4. 二叉树二叉树遍历算法的应用举例遍历算法的应用举例例例1 统计二叉树中叶子结点的个数统计二叉树中叶子结点的个数例例3 求二叉树的深度求二叉树的深度例例4 按层次输出二叉树中的所有结点按层次输出二叉树中的所有结点例例2 创建一棵二叉树创建一棵二叉树48思路：思路：输出叶子结点比较简单，用任何一种遍历算法，凡输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。是左右指针均空者，则为叶子，将其统计并打印出来。 DLR (BiTNode *root) /采用先序遍历的递归算法采用先序遍

28、历的递归算法 if ( root!=NULL ) /非空二叉树条件，还可写成非空二叉树条件，还可写成if (root) if (!root-lchild & !root-rchild) /是叶子结点则统计并打印是叶子结点则统计并打印 sum+; printf (%dn, root-data); DLR (root-lchild); /递归遍历左子树，直到叶子处；递归遍历左子树，直到叶子处； DLR (root-rchild); /递归遍历右子树，直到叶子处；递归遍历右子树，直到叶子处； return(0); 例例1 统计二叉树中叶子结点的个数统计二叉树中叶子结点的个数49注：注：要实现遍历运算

29、必须先把二叉树存入机内。要实现遍历运算必须先把二叉树存入机内。思路：思路：利用利用前序前序遍历来建树遍历来建树（结点值陆续从键盘输入，用（结点值陆续从键盘输入，用DLR为宜）为宜）BiTNode createBTpre( ) BiTNode T; char ch; scanf (“%c”, &ch); if (ch=) T=NULL; else T=( Bintree ) malloc (sizeof (BinTNode); T-data=ch; T-lchild=createBTpre(); T-rchild=createBTpre(); return T;例例2 创建一棵二叉树创建一棵二叉

30、树50算法思路：算法思路：只查各结点后继链表指针，若左只查各结点后继链表指针，若左( (右右) )孩子孩子 的左的左( (右右) )指针非空，则层次数加指针非空，则层次数加1 1；否则；否则 函数返回。函数返回。当当T= NULLT= NULL时时, ,深度为深度为0;0;否则否则, T, T的深度的深度= MAX= MAX左子树深度左子树深度, ,右子树深度右子树深度+1;+1; 例例3 求二叉树的深度求二叉树的深度51算法思路：算法思路：既然要求从上到下，从左到右，则既然要求从上到下，从左到右，则利用利用 队列队列存放各子树结点的指针是个好办法，存放各子树结点的指针是个好办法， 而不必拘泥

31、于递归算法。而不必拘泥于递归算法。技巧：技巧：当根结点入队后，令其左、右孩子结点入队，当根结点入队后，令其左、右孩子结点入队， 而根结点以外的结点出队时又令它的左右孩子而根结点以外的结点出队时又令它的左右孩子 结点入队，结点入队，由此便可产生按层次输出的效果。由此便可产生按层次输出的效果。 A B CD E例例4 按层次输出二叉树中的所有结点按层次输出二叉树中的所有结点52算法思路：算法思路：完全二叉树的特点是：没有左子树空而右完全二叉树的特点是：没有左子树空而右 子树单独存在的情况子树单独存在的情况( (前前k-1k-1层都是满的，层都是满的， 且第且第k k层左边也满）层左边也满）。技巧技

32、巧: : 按层序遍历方式，先把所有结点按层序遍历方式，先把所有结点（不管当前结（不管当前结 点是否有左右孩子）点是否有左右孩子）都入队列都入队列. .若为完全二叉树若为完全二叉树, , 则层序遍历时得到的肯定是一个则层序遍历时得到的肯定是一个连续的不包含连续的不包含 空指针的序列空指针的序列. .如果序列中出现了空指针，则说如果序列中出现了空指针，则说 明不是完全二叉树。明不是完全二叉树。例例5 判断二叉树是否为完全二叉树判断二叉树是否为完全二叉树53问：问：用二叉链表法用二叉链表法（l_child, r_child）存储包含存储包含n个结点的个结点的 二叉树，结点的指针区域中会有多少个空指针

33、？二叉树，结点的指针区域中会有多少个空指针？分析：分析：用二叉链表存储包含用二叉链表存储包含n n个结点的二叉树，结点必有个结点的二叉树，结点必有2n 个链域个链域（见二叉链表数据类型说明）（见二叉链表数据类型说明）。思考：思考：二叉链表空间效率这么低，能否利用这些空闲区存放二叉链表空间效率这么低，能否利用这些空闲区存放 有用的信息或线索？有用的信息或线索？我们可以用它来存放当前结点的直接前驱和后继等线索，我们可以用它来存放当前结点的直接前驱和后继等线索， 以加快查找速度。以加快查找速度。所以，所以， 空指针数目空指针数目2n(n-1)=n+1个个。n+1 除根结点外，二叉树中每一个结点除根结

34、点外，二叉树中每一个结点有且仅有一个双亲有且仅有一个双亲（直接（直接前驱），所以只会有前驱），所以只会有n1个结点的链域存放指针，指向非空子个结点的链域存放指针，指向非空子女结点（即直接后继）。女结点（即直接后继）。54二.线索二叉树线索二叉树（Threaded Binary Tree）普通二叉树只能找到结点的左右孩子信息，普通二叉树只能找到结点的左右孩子信息，而该结点而该结点的直接前驱和直接后继只能在遍历过程中获得。的直接前驱和直接后继只能在遍历过程中获得。若将若将遍历后遍历后对应的有关前驱和后继对应的有关前驱和后继预存预存起来，则从起来，则从第第一个结点一个结点开始就能很快开始就能很快“顺

35、藤摸瓜顺藤摸瓜”而遍历整个树了。而遍历整个树了。两种解决方法：两种解决方法：增加两个域：增加两个域：fwd和和bwd；存放前驱指针存放前驱指针存放后继指针存放后继指针如何预存这类信息？如何预存这类信息？例如中序遍历结果：例如中序遍历结果：B D C E A F H G，实际上，实际上已将二叉已将二叉树转为树转为线性排列线性排列，显然具有唯一前驱和唯一后继。，显然具有唯一前驱和唯一后继。利用空链域（利用空链域（n+1个空链域）个空链域）55规定：规定：1）若结点有左子树，则）若结点有左子树，则lchild指向其左孩子；指向其左孩子； 否则，否则， lchild指向其直接前驱指向其直接前驱(即线索

36、即线索)；2）若结点有右子树，则）若结点有右子树，则rchild指向其右孩子；指向其右孩子； 否则，否则， rchild指向其直接后继指向其直接后继(即线索即线索) 。为区别两种不同情况，特增加两个标志域（各为区别两种不同情况，特增加两个标志域（各1bit)lchilddatarchild约定约定:当当Tag域为域为0时时,表示表示正常正常情况情况;当当Tag域为域为1时时,表示表示线索线索情况情况.右孩子或后继右孩子或后继左孩子或前驱左孩子或前驱LTagRTag1. 线索二叉树的定义线索二叉树的定义56附：有关线索二叉树的几个术语：附：有关线索二叉树的几个术语： 线索链表：线索链表：用用含含

37、Tag的结点样式所构成的二叉链表的结点样式所构成的二叉链表 线线 索：索：指向结点前驱和后继的指针指向结点前驱和后继的指针线索二叉树：线索二叉树：加上线索的二叉树加上线索的二叉树 线线 索索 化：化：对二叉树以对二叉树以某种次序遍历某种次序遍历使其变为线索二使其变为线索二叉树的过程叉树的过程讨论：讨论：增加了前驱和后继等线索有什么好处？增加了前驱和后继等线索有什么好处？能方便找出当前结点的前驱和后继，不用能方便找出当前结点的前驱和后继，不用堆栈也能遍历整个树。堆栈也能遍历整个树。1. 线索二叉树的定义线索二叉树的定义57data AGEIDJHCFBltag0011110101rtag0001

38、010111AGEIDJHCFB例：例：某某先序遍历先序遍历结果如下表所示，请画出对应的结果如下表所示，请画出对应的二叉树。二叉树。 （多带了两个标志！）（多带了两个标志！）582. 线索二叉树的生成线索二叉树的生成线索化过程就是线索化过程就是在遍历过程中修改空指针在遍历过程中修改空指针的过程：的过程：将空的将空的lchild改为结点的直接前驱；改为结点的直接前驱；将空的将空的rchild改为结点的直接后继。改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为非空指针呢？仍然指向孩子结点（称为“正常情况正常情况”）59ABCGEIDHFroot悬空？悬空？悬空？悬空？解：解：该二叉树中序遍历

39、结果为该二叉树中序遍历结果为: : H, D, I, B, E, A, F, C, G所以添加线索应当按如下路径进行：所以添加线索应当按如下路径进行：为避免悬空为避免悬空态，应增设态，应增设一个头结点一个头结点例例1 1：画出以下二叉树对应的画出以下二叉树对应的中序中序线索二叉树。线索二叉树。6000A00C00B11E11F11G00D11I11H注：注：此图中序遍历结果为此图中序遍历结果为: : H, D, I, B, E, A, F, C, G0-root0对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：61例例2：给定如图所示二叉树给定如图所示二叉树T T，

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

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

42、域若若pre-rchildNULL, 则则pre-pre-RtagRtag1;pre-rchild=p; /p存入其前驱结点存入其前驱结点pre的右的右空域空域63Status InorderThreading(BiThrTree & Thrt, BiThrTree T) /中序遍历二叉树中序遍历二叉树T,并将其中序线索化并将其中序线索化, Thrt 指向头结点指向头结点. if ( ! (Thrt = (BiThrTree) malloc ( sizeof (BiThrnode) ) ) exit ( OVERFLOW ) ; Thrt -LTag = Link; Thrt -RTag =

43、Thead; / 建头结点建头结点 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; / InO

44、rderThreading64void 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); /右子树线索化右子树线索化 / InThreading653. 线索二叉树

45、的遍历线索二叉树的遍历理论上，只要找到序列中的理论上，只要找到序列中的第一个结点第一个结点，然后，然后依次访依次访问结点的后继问结点的后继直到后继为空时结束。直到后继为空时结束。在线索化二叉树中，并不是每个结点都能直接找到其在线索化二叉树中，并不是每个结点都能直接找到其后继的，后继的，当标志为当标志为0时，时，R_child= =右孩子地址指针，并非后继！右孩子地址指针，并非后继！需要通过一定运算才能找到它的后继。需要通过一定运算才能找到它的后继。以以中序线索二叉树中序线索二叉树为例：为例：对叶子结点（对叶子结点（RTag=1），直接后继指针就在其），直接后继指针就在其rchild域内；域内；

46、对其他结点（对其他结点（RTag=0），直接后继是其），直接后继是其右子树最左下的结点右子树最左下的结点；（因为中序遍历规则是（因为中序遍历规则是LDR，）66 Status InorderTraverse_Thr(BiThrTree T) P=T-lchild; /p指向根结点；指向根结点； while( p!=T) / 空树或遍历结束时，空树或遍历结束时，p=T while (p-LTag=link) p=p-lchild; /先找到中序遍历起点先找到中序遍历起点 if (!visit(p-data) return ERROR; /访问最左结点访问最左结点 while(p-RTag=Thr

47、ead & p-rchild!=T) /p-rchild=T即为最后一个结点即为最后一个结点 p=p-rchild; Visit(p-data); /若有后继标志，则直接提取若有后继标志，则直接提取p-rchild中线索并访问后继结点；中线索并访问后继结点； p=p-rchild; /当前结点右域不空当前结点右域不空或或已经找好了后继已经找好了后继，则一律从结点，则一律从结点的右子树开始重复的右子树开始重复 的全部过程。的全部过程。 return OK; / InOrderTraverse_Thr线索二叉树的线索二叉树的中序中序遍历算法遍历算法（算法算法6.5, 参见教材参见教材P134）67

48、算法流程：算法流程：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演演示示程程序序686.4 树和森林树和森林一一. 树和森林与二叉树的转换树和森林与二叉树的转换二二. 树和森林的存储方式树和森林的存储方式三三. 树和森林的遍历树和森林的遍历69一一. .树和森林与二叉树的转换树和森林与二叉树的转换转换步骤：转换步骤：step1: 将树中同一结点的兄弟相连将树中同一结点的兄弟相连; ;step2: 保留结

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

50、自转为二叉树； 依次连到前一个二叉树的右子树上。依次连到前一个二叉树的右子树上。讨论讨论3：森林如何转为二叉树？森林如何转为二叉树？法二：法二：森林直接变兄弟，再转为二叉树森林直接变兄弟，再转为二叉树（参见教材（参见教材P138图图6.17，两种方法都有转换示意图），两种方法都有转换示意图）即即F=T1, T2, ,Tm B=root, LB, RB73ABCDEFGHJIABCDEFGHJIBCDEFGHJI森林转二叉树举例：森林转二叉树举例：（法二）（法二）兄弟相连兄弟相连 长兄为父长兄为父孩子靠左孩子靠左 头根为根头根为根 74讨论讨论4 4：二叉树如何还原为森林？：二叉树如何还原为森林

51、？要点：要点：把最右边的子树变为森林，其余右子树变为兄弟把最右边的子树变为森林，其余右子树变为兄弟 ABCDEFGHJIABCDEFGHJIEFABCDGHJI即即B=root, LB, RB F=TB=root, LB, RB F=T1 1, T, T2 2, , ,T,Tm m 75二二. .树和森林的存储方式树和森林的存储方式树有三种常用存储方式：树有三种常用存储方式：双亲表示法双亲表示法 孩子表示法孩子表示法 孩子兄弟表示法孩子兄弟表示法 (1)(1)用双亲表示法来存储用双亲表示法来存储思路：思路：用一组用一组连续空间连续空间来存储树的结点，同时在每个来存储树的结点，同时在每个结点中结

52、点中附设一个指示器附设一个指示器，指示其双亲结点在链表中的，指示其双亲结点在链表中的位置。位置。parentsdata结点结构结点结构dataparents1树结构树结构 23n76缺点：求结点的孩子时需要遍历整个结构。缺点：求结点的孩子时需要遍历整个结构。01234567812233ABCDEFGHI-1001例例1: 双亲表示法双亲表示法77思路：思路：将每个结点的孩子排列起来，形成一个带表头将每个结点的孩子排列起来，形成一个带表头（装父结点）的线性表（装父结点）的线性表（n n个结点要设立个结点要设立n n个链表）；个链表）；再将再将n n个表头用数组存放起来，这样就形成一个混合个表头用

53、数组存放起来，这样就形成一个混合结构。结构。例如例如：abecdfhgdefghgfedcbah12345678(2)(2)用孩子表示法来存储用孩子表示法来存储bc78思路：思路：用二叉链表来表示树，但链表中的两个用二叉链表来表示树，但链表中的两个指针域含义不同。指针域含义不同。左指针指向该结点的第一个孩子；左指针指向该结点的第一个孩子；右指针指向该结点的下一个兄弟结点。右指针指向该结点的下一个兄弟结点。nextsiblingdatafirstchild(3)(3)用孩子兄弟表示法来存储用孩子兄弟表示法来存储指向左孩子指向左孩子指向右兄弟指向右兄弟79abecdfhgbacedfgh问：问：树

54、树二叉树的二叉树的“连线连线抹线抹线旋转旋转” 如如何由计算机自动实现？何由计算机自动实现？答：答：用用“左孩子右兄弟左孩子右兄弟”表示法来存储即可。表示法来存储即可。 例如例如：801. 树的遍历树的遍历:按层次遍历按层次遍历:先根先根(次序次序)遍历遍历:后根后根(次序次序)遍历遍历:若树不空，则先访问根结点，然后依次先根遍历各若树不空，则先访问根结点，然后依次先根遍历各棵子树。棵子树。若树不空，则先依次后根遍历各棵子树，然后访问根若树不空，则先依次后根遍历各棵子树，然后访问根结点。结点。若树不空，则自上而下自左至右访问树中每个结点。若树不空，则自上而下自左至右访问树中每个结点。三三. .

55、树和森林的遍历树和森林的遍历81 A B C DE F G H I J K层次遍历时顶点的访问次序：层次遍历时顶点的访问次序： 先根遍历时顶点的访问次序：先根遍历时顶点的访问次序：A B E F C D G H I J K后根遍历时顶点的访问次序：后根遍历时顶点的访问次序：E F B C I J K H G D AA B C D E F G H I J K82层次遍历时顶点的访问次序：层次遍历时顶点的访问次序： A B C DE F G H I J K先根遍历时顶点的访问次序：先根遍历时顶点的访问次序：A B E F C D G H I J K后根遍历时顶点的访问次序：后根遍历时顶点的访问次序

56、：E F B C I J K H G D AA B C D E F G H I J K83 B C DE F G H I J K1. .森林中第一棵树的根结点；森林中第一棵树的根结点；2. .森林中第一棵树的子树森林中第一棵树的子树 森林；森林；3. .森林中其它树构成的森林。森林中其它树构成的森林。可以分解成三部分：可以分解成三部分：2. 森林的遍历森林的遍历84若森林不空，则若森林不空，则访问森林中第一棵树的根结点访问森林中第一棵树的根结点;先序遍历先序遍历森林中第一棵树的子树森林森林中第一棵树的子树森林;先序遍历先序遍历森林中森林中(除第一棵树之外除第一棵树之外)其余树构成的森林。其余树

57、构成的森林。先序遍历先序遍历2. 森林的遍历森林的遍历即：依次从左至右对森林中的每一棵即：依次从左至右对森林中的每一棵树树进行进行先根遍历先根遍历。85 中序遍历中序遍历若森林不空，则若森林不空，则中序遍历中序遍历森林中第一棵树的子树森林森林中第一棵树的子树森林;访问森林中第一棵树的根结点访问森林中第一棵树的根结点;中序遍历中序遍历森林中森林中(除第一棵树之外除第一棵树之外)其余树构成的森林。其余树构成的森林。即：依次从左至右对森林中的每一棵即：依次从左至右对森林中的每一棵树树进行进行后根遍历后根遍历。2. 森林的遍历森林的遍历86 树的遍历和二叉树遍历树的遍历和二叉树遍历的对应关系的对应关系

58、 ？先根遍历先根遍历后根遍历后根遍历树树二叉树二叉树森林森林先序遍历先序遍历先序遍历先序遍历中序遍历中序遍历中序遍历中序遍历876.5 Huffman树及其应用树及其应用一、最优二叉树（一、最优二叉树（赫夫曼赫夫曼树）树）二、二、Huffman树的构造树的构造三、三、Huffman编码编码88路路 径径：路径长度路径长度：树的路径长度树的路径长度：带权路径长度带权路径长度：树的带权路径长度树的带权路径长度：赫赫 夫夫 曼曼 树：树：一一. .最优二叉树（最优二叉树（赫夫曼赫夫曼树）树）由一结点到另一结点间的分支所构成。由一结点到另一结点间的分支所构成。路径上的分支数目。路径上的分支数目。从树根

59、到从树根到每一结点每一结点的路径长度之和。的路径长度之和。结点到根的路径长度与结点上权的乘积。结点到根的路径长度与结点上权的乘积。debacf g树中所有树中所有叶子结点叶子结点的带权路径长度之和。的带权路径长度之和。带权路径长度最小的树。带权路径长度最小的树。ae的路径长度的路径长度树长度树长度2106.5 Huffman树及其应用树及其应用89Huffman树简介：树简介：树的带权路径长度如何计算？树的带权路径长度如何计算？WPLWPL = = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)WPL=36WPL=46WPL= 3

60、5哈夫曼树则是：哈夫曼树则是：WPL WPL 最小的树。最小的树。Huffman树树Weighted Path Length90构造赫夫曼树的基本思想：构造赫夫曼树的基本思想：二二. .Huffman树的构造树的构造构造构造Huffman树的步骤（即树的步骤（即Huffman算法）：算法）：91二二. .Huffman树的构造树的构造构造构造Huffman树的步骤（即树的步骤（即Huffman算法）：算法）：92设有设有4个字符个字符d,i,a,n，出现的频度分别为，出现的频度分别为7,5,2,4， 怎样编码才能使它们组成的报文在网络中传得最快？怎样编码才能使它们组成的报文在网络中传得最快？法