数据结构铜陵学院课件

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.树的定义树的定义注注1：过去许多书籍中都定义树为过去许多书籍中都定义树为n1，曾经有，曾经有“空树不是空树不是树树”的说法，但现在树的定义已修改。的说法，但现在树的定义已修改。注注2：树的定义具有树的定义具有递归性递归性，即树中还有树。，即树中还有树。由一个或多个由一个或多个(n0n0)结点组成的有限集合结点组成的有限集合T T，有，有且仅有且仅有一个结点称为根一个结点称为根（rootroot），），当当n1n1时，其余的时，其余的结点分为结点分为m(m0)m(m0)个个互不相交互不相交的有限集合的有限集合T1,T2T1,T2，TmTm。每个集合本身又是棵树，被称作这个根的。每个集合本身又是棵树，被称作这个根的子树子树 。5树的表示法有几种：树的表示法有几种：图形表示法图形表示法嵌套集合表示法嵌套集合表示法广义表表示法广义表表示法目录表示法目录表示法左孩子右兄弟表示法左孩子右兄弟表示法这些表示法的示意图这些表示法的示意图参见教材参见教材P120P120树的抽象数据类型定义树的抽象数据类型定义参参见教材见教材P118-119P118-1196图形表示法：图形表示法：教师教师学生学生其他人员其他人员20112011级级 20122012级级 20132013级级20142014级级铜陵学院铜陵学院会计学院会计学院数计学院数计学院金融学院金融学院叶子叶子根根子树子树7广义表表示法广义表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)根作为根作为由子树森林组成的由子树森林组成的表的名字写在表的左边表的名字写在表的左边datalink 1 link 2.link n麻烦问题：应当开设多少个链域麻烦问题：应当开设多少个链域?8左孩子右兄弟表示法左孩子右兄弟表示法A AB BC CD DE EF FGGHHI IJ JKKL LMM数据数据左孩子左孩子 右兄弟右兄弟(A(B(E(K,L),F),C(G),D(H(M),I,J)9 树的抽象数据类型定义树的抽象数据类型定义（见教材（见教材P118-P118-119119）ADT Tree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT Tree若若D为空集，则称为空树；为空集，则称为空树；/允许允许n=0若若D中仅含一个数据元素，则中仅含一个数据元素，则R为空集；为空集；其他情况下的其他情况下的R存在二元关系：存在二元关系：root 唯一唯一 /关于根的说明关于根的说明 DjDk=/关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有15个个102.若干术语若干术语即上层的那个结点即上层的那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点ABCGEIDHFJMLK 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集棵不相交的树的集合合(例如删除例如删除A后的子树个数后的子树个数)双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙结点各子树从左至右有序，不能互换（左为第一）结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。结点各子树可互换位置。112.若干术语（续）若干术语（续）即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数（有几个直接后继就是几度，（有几个直接后继就是几度，亦称亦称“次数次数”）结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)ABCGEIDHFJMLK从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点（也称为内部结点）的结点（也称为内部结点）所有结点度中的最大值（所有结点度中的最大值（Max各结点的度各结点的度）指所有结点中最大的层数（指所有结点中最大的层数（Max各结点的层次各结点的层次）问：问：右上图中的结点数右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4123.树的逻辑结构树的逻辑结构(特点特点)：一对多（一对多（1:n1:n），有多个直接后继（如家谱），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且树、目录树等等），但只有一个根结点，且子树之间互不相交子树之间互不相交。4.树的存储结构树的存储结构 讨论讨论1：树是非线性结构，该怎样存储？树是非线性结构，该怎样存储？仍然有顺序存储、链式存储等方式。仍然有顺序存储、链式存储等方式。13讨论讨论3：树的树的链式存储链式存储方案应该怎样制定？方案应该怎样制定？可规定为：可规定为：从上至下、从左至右从上至下、从左至右将树的结点依次存入内存。将树的结点依次存入内存。重大缺陷：复原困难（不能唯一复原就没有实用价值）。重大缺陷：复原困难（不能唯一复原就没有实用价值）。讨论讨论2：树的树的顺序存储顺序存储方案应该怎样制定？方案应该怎样制定？可用多重链表：可用多重链表：一个前趋指针，一个前趋指针，n n个后继指针。个后继指针。细节问题：细节问题：树中结点的结构类型样式该如何设计？树中结点的结构类型样式该如何设计？即应该设计成即应该设计成“等长等长”还是还是“不等长不等长”？缺点：缺点：等长结构太浪费（每个结点的度不一定相同）；等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型）。不等长结构太复杂（要定义好多种结构类型）。解决思路：解决思路：先研究最简单、最有规律的树，然后设法把先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。一般的树转化为简单树。二叉树二叉树二叉树二叉树145.树的运算树的运算 要明确：要明确：1.普普通通树树（即即多多叉叉树树）若若不不转转化化为为二二叉叉树树，则则运运算很难实现。算很难实现。2.二二叉叉树树的的运运算算仍仍然然是是插插入入、删删除除、修修改改、查查找找、排排序序等等，但但这这些些操操作作必必须须建建立立在在对对树树结结点点能能够够“遍历遍历”的基础上！的基础上！（遍遍历历指指每每个个结结点点都都被被访访问问且且仅仅访访问问一一次次，不遗漏不重复）。不遗漏不重复）。本章重点：二叉树的表示和实现本章重点：二叉树的表示和实现156.2 6.2 二叉树二叉树为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “叉叉”的树？的树？二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。可以证明，所有树都能转为唯一对应的二叉树，不失一般性。1.二叉树的定义二叉树的定义2.二叉树的性质二叉树的性质3.二叉树的存储结构二叉树的存储结构（二叉树的运算（二叉树的运算见见6.3节节）161.1.1.1.二叉树的定义二叉树的定义二叉树的定义二叉树的定义定义：定义：是是n（n0）个结点的有限集合，由一个根结点以及两）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为棵互不相交的、分别称为左子树和右子树左子树和右子树的二叉树组成的二叉树组成。逻辑结构：逻辑结构：一对二（一对二（1：2）基本特征基本特征:每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）；的结点）；左子树和右子树次序不能颠倒（有序树）。左子树和右子树次序不能颠倒（有序树）。基本形态：基本形态：问：具有问：具有问：具有问：具有3 3 3 3个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？5种种/2种种17二叉树的抽象数据类型定义二叉树的抽象数据类型定义（见教材（见教材P P121-122121-122）ADT BinaryTree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT BinaryTree若若D=，则，则R=；若若D，则，则R=H；存在二元关系：；存在二元关系：root 唯一唯一 /关于根的说明关于根的说明 DjDk=/关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明 /关于左子树和右子树的说明关于左子树和右子树的说明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有20个个182.2.2.2.二叉树的性质二叉树的性质二叉树的性质二叉树的性质 (3+2)(3+2)(3+2)(3+2)讨论讨论1 1：第：第i i层的结点数至多是多少？层的结点数至多是多少？（利用二进制性质可轻松求出）（利用二进制性质可轻松求出）性质性质1:1:在二叉树的第在二叉树的第i i层上至多有层上至多有2 2 2 2i-1i-1i-1i-1个结点（个结点（i0i0）。）。性质性质2:2:深度为深度为k k的二叉树至多有的二叉树至多有2 2 2 2k k k k-1-1-1-1个结点（个结点（k0k0）。）。2 2i-1i-1个个提问：第提问：第i i层上至少有层上至少有 个结点？个结点？1 1讨论讨论2 2：深度为：深度为k k的二叉树，至多有多少个结点？的二叉树，至多有多少个结点？（利用二进制性质可轻松求出）（利用二进制性质可轻松求出）2 2k k-1-1提问：深度为提问：深度为k k时至少有时至少有 个结点？个结点？k k19讨论讨论3 3：二叉树的叶子数和度为：二叉树的叶子数和度为2 2的结点数之间有关系吗的结点数之间有关系吗？性质性质3:3:对于任何一棵二叉树，若对于任何一棵二叉树，若2 2度的结点数有度的结点数有n n2 2个，个，则叶子数（则叶子数（n n0 0）必定为必定为n n2 21 1（即（即n0=n2+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 1ABCGEIDHFJ20对于两种特殊形式的二叉树（对于两种特殊形式的二叉树（满二叉树和完全二叉树满二叉树和完全二叉树），），还特别具备以下还特别具备以下2 2个性质：个性质：性质性质4:4:具有具有n n个结点的完全二叉树的深度必为个结点的完全二叉树的深度必为loglog2 2nn1 1性质性质5:5:对完全二叉树，若从上至下、从左至右编号，则对完全二叉树，若从上至下、从左至右编号，则编号为编号为i 的结点，其左孩子编号必为的结点，其左孩子编号必为2i，其右孩子编号必，其右孩子编号必为为2i1；其双亲的编号必为；其双亲的编号必为i/2（i1 时为根时为根,除外除外）。）。证证明明：根根据据性性质质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 n1)f=n*fact(n-1);else f=1;return(f);34先序遍历算法先序遍历算法DLR(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)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语句抹去，语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的遍历算法的访问路径是相同的，只是访问结点的时机不同访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径从虚线的出发点到终点的路径上，每个结点经过上，每个结点经过3次次。AFEDCBG第第1次经过时访问先序遍历次经过时访问先序遍历第第2次经过时访问中序遍历次经过时访问中序遍历第第3次经过时访问后序遍历次经过时访问后序遍历2.2.二叉树遍历的时间效率和空间效率二叉树遍历的时间效率和空间效率时间效率时间效率:O(n)O(n)O(n)O(n)/每个结点只访问一次每个结点只访问一次空间效率空间效率:O(n)O(n)O(n)O(n)/栈占用的最大辅助空间栈占用的最大辅助空间（精确值：树深为（精确值：树深为k k的递归遍历需要的递归遍历需要k+1k+1个辅助单元！）个辅助单元！）36例：例：【严题集严题集6.42】编写递归算法，计算二叉编写递归算法，计算二叉树中叶子结点的数目。树中叶子结点的数目。思路：思路：输出叶子结点比较简单，用任何一种遍历算法，凡输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。是左右指针均空者，则为叶子，将其统计并打印出来。DLR(liuyu*root)/采用中序遍历的递归算法采用中序遍历的递归算法 if(root!=NULL)/非空二叉树条件，还可写成非空二叉树条件，还可写成if(root)if(root)if(!root-lchild&!root-rchild)/是叶子结点则统计并打印是叶子结点则统计并打印 sum+;printf(%dn,root-data);DLR(root-lchild);/递归遍历左子树，直到叶子处；递归遍历左子树，直到叶子处；DLR(root-rchild);/递归遍历右子树，直到叶子处；递归遍历右子树，直到叶子处；return(0);37注：要实现遍历运算必须先把二叉树存入机内。注：要实现遍历运算必须先把二叉树存入机内。思路：思路：利用利用前序前序遍历来建树遍历来建树（结点值陆续从键盘输入，用（结点值陆续从键盘输入，用DLR为宜为宜）Bintree createBTpre()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.1.1.求二叉树深度，或从求二叉树深度，或从求二叉树深度，或从求二叉树深度，或从x x x x结点开始的子树深度。结点开始的子树深度。结点开始的子树深度。结点开始的子树深度。算法思路：算法思路：只查各结点后继链表指针，若左只查各结点后继链表指针，若左(右右)孩子的左孩子的左(右右)指针非空，则层次数加指针非空，则层次数加1 1；否则函数返回。；否则函数返回。技巧：技巧：递归时应当递归时应当从叶子开始向上计数，层深者保留。从叶子开始向上计数，层深者保留。否则否则不易确定层数。不易确定层数。2.2.2.2.按层次输出二叉树中所有结点。按层次输出二叉树中所有结点。按层次输出二叉树中所有结点。按层次输出二叉树中所有结点。算法思路：算法思路：既然要求从上到下，从左到右，则既然要求从上到下，从左到右，则利用队列利用队列存放存放各子树结点的指针是个好办法，而不必拘泥于递归算法。各子树结点的指针是个好办法，而不必拘泥于递归算法。技技巧巧：当当根根结结点点入入队队后后，令令其其左左、右右孩孩子子结结点点入入队队，而而左左孩孩子子出出队队时时又又令令它它的的左左右右孩孩子子结结点点入入队队，由由此此便便可可产产生生按按层次输出的效果。层次输出的效果。A B CD E393 3 3 3 中序遍历的非递归中序遍历的非递归中序遍历的非递归中序遍历的非递归(迭代迭代迭代迭代)算法算法算法算法算法思路：算法思路：若不用递归，则要实现二叉树遍历的若不用递归，则要实现二叉树遍历的“嵌套嵌套”规规则，必用堆栈。可直接用则，必用堆栈。可直接用whilewhile语句和语句和push/poppush/pop操作。操作。参见教参见教材材P130-131P130-131程序。程序。4.4.4.4.判别给定二叉树是否为完全二叉树（即顺序二叉树）。判别给定二叉树是否为完全二叉树（即顺序二叉树）。判别给定二叉树是否为完全二叉树（即顺序二叉树）。判别给定二叉树是否为完全二叉树（即顺序二叉树）。算法思路：算法思路：完全二叉树的特点是：没有左子树空而右子树单完全二叉树的特点是：没有左子树空而右子树单独存在的情况独存在的情况(前前k-1k-1层都是满的，且第层都是满的，且第k k层左边也满）层左边也满）。技技巧巧:按按层层序序遍遍历历方方式式，先先把把所所有有结结点点（不不管管当当前前结结点点是是否否有有左左右右孩孩子子）都都入入队队列列.若若为为完完全全二二叉叉树树,则则层层序序遍遍历历时时得得到到的的肯肯定定是是一一个个连连续续的的不不包包含含空空指指针针的的序序列列.如如果果序序列列中中出出现现了了空空指针，则说明不是完全二叉树。指针，则说明不是完全二叉树。40特别讨论：特别讨论：特别讨论：特别讨论：若已知先序若已知先序若已知先序若已知先序/后序遍历结果和中序遍历后序遍历结果和中序遍历后序遍历结果和中序遍历后序遍历结果和中序遍历结果，能否结果，能否结果，能否结果，能否“恢复恢复恢复恢复”出二叉树？出二叉树？出二叉树？出二叉树？【严题集严题集6.31】证明：由一棵二叉树的先序序列和中序证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。序列可唯一确定这棵二叉树。例：例：已知一棵二叉树的已知一棵二叉树的中序序列中序序列和和后序序列后序序列分别是分别是BDCEAFHG 和和 DECBHGFA，请画出这棵二叉树。，请画出这棵二叉树。分析：分析：由后序遍历特征，根结点必在后序序列尾部由后序遍历特征，根结点必在后序序列尾部（即（即A A）；由由中中序序遍遍历历特特征征，根根结结点点必必在在其其中中间间，而而且且其其左左部部必必全全部部是是左子树子孙左子树子孙（即（即BDCEBDCE），其右部必全部是右子树子孙，其右部必全部是右子树子孙（即（即FHGFHG）；继继而而，根根据据后后序序中中的的DECBDECB子子树树可可确确定定B B为为A A的的左左孩孩子子，根根据据HGFHGF子串可确定子串可确定F F为为A A的右孩子；以此类推。的右孩子；以此类推。41中序遍历：中序遍历：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 EGHABBFF42问：问：用二叉链表法（用二叉链表法（l_child,r_child）存储包含）存储包含n个结点的个结点的二叉树，结点的指针区域中会有多少个空指针？二叉树，结点的指针区域中会有多少个空指针？分分析析：用用二二叉叉链链表表存存储储包包含含n n个个结结点点的的二二叉叉树树，结结点点必必有有2n个链域个链域（见二叉链表数据类型说明）（见二叉链表数据类型说明）。除除根根结结点点外外，二二叉叉树树中中每每一一个个结结点点有有且且仅仅有有一一个个双双亲亲（直直接接前前驱驱），所所以以只只会会有有n n1 1个个结结点点的的链链域域存存放放指指针针，指指向非空子女结点（即直接后继）。向非空子女结点（即直接后继）。思考：思考：二叉链表空间效率这么低，能否利用这些空闲区存放二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？有用的信息或线索？我们可以用它来存放当前结点的直接前驱和后继等线索，我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。以加快查找速度。所以，所以，空指针数目空指针数目2n(n-1)=n+1个个。n+143二、线索二叉树线索二叉树（Threaded Binary Tree）普通二叉树只能找到结点的左右孩子信息，普通二叉树只能找到结点的左右孩子信息，而该结点而该结点的直接前驱和直接后继只能在遍历过程中获得。的直接前驱和直接后继只能在遍历过程中获得。若将若将遍历后遍历后对应的有关前驱和后继对应的有关前驱和后继预存预存起来，则从起来，则从第第一个结点一个结点开始就能很快开始就能很快“顺藤摸瓜顺藤摸瓜”而遍历整个树了。而遍历整个树了。两种解决方法：两种解决方法：增加两个域：增加两个域：fwd和和bwd；存放前驱指针存放前驱指针存放后继指针存放后继指针如何预存这类信息？如何预存这类信息？例如中序遍历结果：例如中序遍历结果：B 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指向其直接后继指向其直接后继(即线索即线索)。为区别两种不同情况，特增加两个标志域（各为区别两种不同情况，特增加两个标志域（各1bit)lchilddatarchild约定约定:当当Tag域为域为0时时,表示表示正常正常情况情况;当当Tag域为域为1时时,表示表示线索线索情况情况.右孩子或后继右孩子或后继左孩子或前驱左孩子或前驱LTagRTag45附：有关线索二叉树的几个术语：附：有关线索二叉树的几个术语：线索链表：线索链表：用用含含Tag的结点样式所构成的二叉链表的结点样式所构成的二叉链表 线线 索：索：指向结点前驱和后继的指针指向结点前驱和后继的指针线索二叉树：线索二叉树：加上线索的二叉树加上线索的二叉树 线线 索索 化：化：对二叉树以对二叉树以某种次序遍历某种次序遍历使其变为线索二使其变为线索二叉树的过程叉树的过程讨论：讨论：增加了前驱和后继等线索有什么好处？增加了前驱和后继等线索有什么好处？能方便找出当前结点的前驱和后继，不用能方便找出当前结点的前驱和后继，不用堆栈也能遍历整个树。堆栈也能遍历整个树。46dataAGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例：例：某某先序遍历先序遍历结果如下表所示，请画出对应的结果如下表所示，请画出对应的二叉树。二叉树。（多带了两个标志！）（多带了两个标志！）472.2.线索二叉树的生成线索二叉树的生成线索化过程就是线索化过程就是在遍历过程中修改空指针在遍历过程中修改空指针的过程：的过程：将空的将空的l lchildchild改为结点的直接前驱；改为结点的直接前驱；将空的将空的r rchildchild改为结点的直接后继。改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为非空指针呢？仍然指向孩子结点（称为“正常情况正常情况”）48ABCGEIDHFroot悬空悬空？悬空？悬空？解：解：该二叉树中序遍历结果为该二叉树中序遍历结果为:H,D,I,B,E,A,F,C,G所以添加线索应当按如下路径进行：所以添加线索应当按如下路径进行：为避免悬空为避免悬空态，应增设态，应增设一个头结点一个头结点例例1 1：画出以下二叉树对应的画出以下二叉树对应的中序中序线索二叉树。线索二叉树。4900A00C00B11E11F11G00D11I11H注：此图中序遍历结果为注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G0-root0对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：50例例2 2：【2000年计算机系考研题年计算机系考研题】给定如图所示给定如图所示二叉树二叉树T T，请画出与其对应的中序线索二叉树。，请画出与其对应的中序线索二叉树。2825405560330854解解:因为中序遍历序列是：因为中序遍历序列是：5555 40 25 60 40 25 60 2828 08 33 08 33 5454对应线索树应当按此规律连线，即对应线索树应当按此规律连线，即在原二叉树中添加虚线。在原二叉树中添加虚线。NILNILNILNIL51线索二叉树的生成算法线索二叉树的生成算法（算法算法6.6,见教材见教材P134）目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后 继。继。注解：为方便添加结点的前驱或后继，需要设置两个指针：注解：为方便添加结点的前驱或后继，需要设置两个指针：p指针指针当前结点之指针；当前结点之指针；pre指针指针前驱结点之指针。前驱结点之指针。技巧：技巧：当结点当结点p的左的左/右域为空右域为空时，只改写它的左域（装入前驱时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。，而其右域（后继）留给下一结点来填写。或者说，当前结点的指针或者说，当前结点的指针p应当送到前驱结点的空右域中。应当送到前驱结点的空右域中。若若p-lchildNULL,则则p-Ltag=1;p-Ltag=1;p-lp-lchildchildpre;/p/p的前驱结点指针的前驱结点指针pre存入左空域存入左空域若若pre-rchildNULL,则则pre-Rtagpre-Rtag1;pre-rchild=p;/p存入其前驱结点存入其前驱结点pre的右的右空域空域523.3.线索二叉树的遍历线索二叉树的遍历理论上，只要找到序列中的理论上，只要找到序列中的第一个结点第一个结点，然后，然后依次访依次访问结点的后继问结点的后继直到后继为空时结束。直到后继为空时结束。但是，但是，但是，但是，在线索化二叉树中，并不是每个结点都能直接找到其在线索化二叉树中，并不是每个结点都能直接找到其后继的，后继的，当标志为当标志为0 0时，时，R_child=R_child=右孩子地址指针，并非后继！右孩子地址指针，并非后继！需要通过一定运算才能找到它的后继。需要通过一定运算才能找到它的后继。以以中序线索二叉树中序线索二叉树为例：为例：对叶子结点（对叶子结点（RTag=1），直接后继指针就在其），直接后继指针就在其rchild域内；域内；对其他结点（对其他结点（RTag=0），直接后继是其），直接后继是其右子树最左下的结点右子树最左下的结点；（因为中序遍历规则是（因为中序遍历规则是LDR，先左再根再右先左再根再右先左再根再右先左再根再右）53程序注解程序注解 (非递归，且不用栈非递归，且不用栈）：）：P=T-lchild;/从头结点进入到根结点；从头结点进入到根结点；while(p!=T)while(p-LTag=link)p=p-lchild;/先找到中序遍历起点先找到中序遍历起点 if(!visit(p-data)return ERROR;/若起点值为空则出错告警若起点值为空则出错告警 while(p-RTag=Thread)p=p-rchild;Visit(p-data);/若有后继标志，则直接提取若有后继标志，则直接提取p-rchild中线索并中线索并访问后继结点；访问后继结点；p=p-rchild;/当前结点右域不空当前结点右域不空或或已经找好了后继已经找好了后继，则一律从，则一律从结点的右子树开始重复结点的右子树开始重复 的全部过程。的全部过程。Return OK;线索二叉树的线索二叉树的中序中序遍历算法遍历算法（算法算法6.5,参见教材参见教材P134）LTag=0RTag=154算法流程：算法流程：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）由字符串构成的二叉树排序树由字符串构成的二叉树排序树例如，例如，12个球只称个球只称3次分出轻重次分出轻重特点：路径长度带权值特点：路径长度带权值 带权路径长度最短的树，又称带权路径长度最短的树，又称 Huffman树，用途之一是通信中的压缩编码。树，用途之一是通信中的压缩编码。566.4 树和森林1.树和森林与二叉树的转换树和森林与二叉树的转换2.树和森林的存储方式树和森林的存储方式3.树和森林的遍历树和森林的遍历571.树和森林与二叉树的转换树和森林与二叉树的转换转换步骤：转换步骤：step1:step1:将树中同一结点的兄弟相连将树中同一结点的兄弟相连;step2:step2:保留结点的最左孩子连线，删除其它孩保留结点的最左孩子连线，删除其它孩子连线；子连线；step3:step3:将同一孩子的连线绕左孩子旋转将同一孩子的连线绕左孩子旋转4545度角。度角。加线加线抹线抹线旋转旋转讨论讨论1 1：树如何转为二叉树？：树如何转为二叉树？58方法：方法：加加线线抹线抹线旋转旋转 abeidfhgc树转二叉树举例：树转二叉树举例：abeidfhgc兄弟相连兄弟相连长兄为父长兄为父孩子靠左孩子靠左根结点肯定根结点肯定根结点肯定根结点肯定没有右孩子！没有右孩子！没有右孩子！没有右孩子！59讨论讨论2 2：二叉树怎样还原为树？：二叉树怎样还原为树？abeidfhgc要点：把所有右孩子变为兄弟！要点：把所有右孩子变为兄弟！abeidfhgc60法一：法一：各森林先各自转为二叉树；各森林先各自转为二叉树；依次连到前一个二叉树的右子树上。依次连到前一个二叉树的右子树上。讨论讨论3 3：森林如何转为二叉树？：森林如何转为二叉树？法二：法二：森林直接变兄弟，再转为二叉树森林直接变兄弟，再转为二叉树（参见教材（参见教材P138P138图图6.176.17，两种方法都有转换示意图），两种方法都有转换示意图）即即F=TF=T1 1,T,T2 2,T,Tm m B=root,LB,RB B=root,LB,RB61ABCDEFGHJIABCDEFGHJIA ABCDEFGHJI森林转二叉树举例：森林转二叉树举例：（法二）（法二）兄弟相连兄弟相连 长兄为父长兄为父孩子靠左孩子靠左 头根为根头根为根 A A62讨论讨论4 4：二叉树如何还原为森林？：二叉树如何还原为森林？要点：要点：把最右边的子树变为森林，其余右子树变为兄弟把最右边的子树变为森林，其余右子树变为兄弟 ABCDEFGHJIABCDEFGHJIEFABCDGHJI即即B=root,LB,RB F=TB=root,LB,RB F=T1 1,T,T2 2,T,Tm m 632.2.树和森林的存储方式树和森林的存储方式树有三种常用存储方式：树有三种常用存储方式：双亲表示法双亲表示法 孩子表示法孩子表示法 孩子兄弟表示法孩子兄弟表示法 1 1、用双亲表示法来存储、用双亲表示法来存储思路：思路：用一组用一组连续空间连续空间来存储树的结点，同时在每个来存储树的结点，同时在每个结点中结点中附设一个指示器附设一个指示器，指示其双亲结点在链表中的，指示其双亲结点在链表中的位置。位置。parentsdata结点结构结点结构dataparents1树结构树结构 23n64A AB BC CGGE EI ID DHHF F缺点：求结点的孩子时需要遍历整个结构。缺点：求结点的孩子时需要遍历整个结构。01234567812233ABCDEFGHI-1001例例1:双亲表示法双亲表示法65思路：将每个结点的孩子排列起来，形成一个带表头思路：将每个结点的孩子排列起来，形成一个带表头（装父结点）的线性表（装父结点）的线性表（n n个结点要设立个结点要设立n n个链表）；个链表）；再将再将n n个表头用数组存放起来，这样就形成一个混合个表头用数组存放起来，这样就形成一个混合结构。结构。例如例如：abecdfhgdefghgfedcbah123456782 2、用孩子表示法来存储、用孩子表示法来存储bc66思路：思路：用二叉链表来表示树，但链表中的两个用二叉链表来表示树，但链表中的两个指针域含义不同。指针域含义不同。左指针指向该结点的第一个孩子；左指针指向该结点的第一个孩子；右指针指向该结点的下一个兄弟结点。右指针指向该结点的下一个兄弟结点。nextsiblingdatafirstchild3 3、用孩子兄弟表示法来存储、用孩子兄弟表示法来存储指向左孩子指向左孩子指向右兄弟指向右兄弟67abecdfhgbacedfgh问：问：树树转转二叉树的二叉树的“连线连线抹线抹线旋转旋转”如如何由计算机自动实现？何由计算机自动实现？答：答：用用“左孩子右兄弟左孩子右兄弟”表示法来存储即可。表示法来存储即可。存储的过程就是转换的过程！存储的过程就是转换的过程！例如例如：68先序遍历先序遍历F若森林为空，返回；若森林为空，返回；F访问森林中第一棵树的根结点；访问森林中第一棵树的根结点；F先序遍历第一棵树中根结点的子树森林；先序遍历第一棵树中根结点的子树森林；F先序遍历除去第一棵树之后剩余的树构成的森林。先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历中序遍历F若森林为空，返回；若森林为空，返回；F中序遍历森林中第一棵树的根结点的子树森林；中序遍历森林中第一棵树的根结点的子树森林；F访问第一棵树的根结点；访问第一棵树的根结点；F中序遍历除去第一棵树之后剩余的树构成的森林。中序遍历除去第一棵树之后剩余的树构成的森林。森林的遍历森林的遍历ABCDEFGHJI69路路 径径：路径长度路径长度：树的路径长度树的路径长度：带权路径长度带权路径长度：树的带权路径长度树的带权路径长度：霍霍 夫夫 曼曼 树树：6.5 Huffman6.5 Huffman树及其应用树及其应用一、最优二叉树（一、最优二叉树（霍夫曼霍夫曼树）树）由一结点到另一结点间的分支所构成由一结点到另一结点间的分支所构成路径上的分支数目路径上的分支数目从树根到从树根到每一结点每一结点的路径长度之和。的路径长度之和。结点到根的路径长度与结点上权的乘积结点到根的路径长度与结点上权的乘积预备知识：若干术语预备知识：若干术语debacf g树中所有树中所有叶子结点叶子结点的带权路径长度之和的带权路径长度之和带权路径长度最小的树。带权路径长度最小的树。aeae的路径长度的路径长度树长度树长度2 2101070HuffmanHuffman树简介：树简介：树的带权路径长度如何计算？树的带权路径长度如何计算？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 Length71(1)(1)由给定的由给定的由给定的由给定的 n n 个权值个权值个权值个权值 w w0 0,w w1 1,w w2 2,w wn n-1-1，构造具有，构造具有，构造具有，构造具有 n n 棵扩充棵扩充棵扩充棵扩充二叉树的二叉树的二叉树的二叉树的森林森林森林森林F F=T T0 0,T T1 1,T T2 2,T Tn n-1-1 ，其中每一棵扩充二叉树，其中每一棵扩充二叉树，其中每一棵扩充二叉树，其中每一棵扩充二叉树 T Ti i 只有一个带有权值只有一个带有权值只有一个带有权值只有一个带有权值 w wi i 的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。(2)(2)重复以下步骤重复以下步骤重复以下步骤重复以下步骤,直到直到直到直到 F F 中仅剩下一棵树为止：中仅剩下一棵树为止：中仅剩下一棵树为止：中仅剩下一棵树为止：在在在在 F F 中中中中选取两棵根结点的权值最小选取两棵根结点的权值最小选取两棵根结点的权值最小选取两棵根结点的权值最小的扩充二叉树的扩充二叉树的扩充二叉树的扩充二叉树,做为左、做为左、做为左、做为左、右子树构造一棵新的二叉树。置新的二叉树的右子树构造一棵新的二叉树。置新的二叉树的右子树构造一棵新的二叉树。置新的二叉树的右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为根结点的权值为根结点的权值为根结点的权值为其左、右子树上根结点的权值之和其左、右子树上根结点的权值之和其左、右子树上根结点的权值之和其左、右子树上根结点的权值之和。在在在在 F F 中删去这两棵二叉树。中删去这两棵二叉树。中删去这两棵二叉树。中删去这两棵二叉树。把新的二叉树加入把新的二叉树加入把新的二叉树加入把新的二叉树加入 F F。构造霍夫曼树的基本思想：构造霍夫曼树的基本思想：构造构造HuffmanHuffman树的步骤（即树的步骤（即HuffmanHuffman算法）：算法）：权值大的结点用短路径，权值小的结点用长路径权值大的结点用短路径，权值小的结点用长路径权值大的结点用短路径，权值小的结点用长路径权值大的结点用短路径，权值小的结点用长路径。先举例！先举例！72例例1：设有设有4 4个字符个字符d,i,a,nd,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最快的编码是哪个？最快的编码是哪个？是非等长的是非等长的HuffmanHuffman码！码！先要构造先要构造HuffmanHuffman树！树！73操作要点操作要点1 1：对权值的合并、删除与替换对权值的合并、删除与替换在权值集合在权值集合7,5,2,47,5,2,4中，总是合并中，总是合并当前值最小当前值最小的两个权的两个权构造构造HuffmanHuffman树的步骤：树的步骤：注：方框表示外结点（叶子，字符对应的权值），注：方框表示外结点（叶子，字符对应的权值），圆框表示内结点（合并后的权值）。圆框表示内结点（合并后的权值）。74操作要点操作要点2 2：按左按左0 0右右1 1对对HuffmanHuffman树的所有分支编号！树的所有分支编号！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（严题集（严题集6.266.26）：假设用于通信的电文仅由假设用于通信的电文仅由8 8个字母个字母 a,b,c,d,e,f,g,ha,b,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的二进制编码方案的二进制编码方案又如何？又如何？霍夫曼霍夫曼编码的基本思想是：编码的基本思想是：概率大的字符用短码，概率小的用概率大的字符用短码，概率小的用长码。由于长码。由于霍夫曼树的霍夫曼树的WPLWPL最小，最小，说明编码所需要的比特数最说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。少。这种编码已广泛应用于网络通信中。解：解：先将概率放大先将概率放大100100倍，以方便构造哈夫曼树。倍，以方便构造哈夫曼树。权值集合权值集合 w=7,19,2,6,32,3,21,10w=7,19,2,6,32,3,21,10，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。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哈夫曼树哈夫曼树 77对应的哈夫曼编码（左对应的哈夫曼编码（左0右右1）：）：2 23 35 56 6111110107 73232171728282121191940406060100100b bc ca ad de eg gf fh h0 00 00 00 00 01 11 11 11 11 11 11 10 00 0符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman码的码的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 11001100000011110111101110111010101111111111010111011101000001010011100101110111二进制码二进制码二进制码二进制码78另一种结果表示：另一种结果表示：79例例3 3（实验二方案（实验二方案3 3）：设字符集为设字符集为2626个英文字母，其出个英文字母，其出现频度如下表所示。现频度如下表所示。注：若圆满实现了此方案，平时成绩将以满分计。注：若圆满实现了此方案，平时成绩将以满分计。51481156357203251频度频度zyxwvut t字符字符11611882380频度频度p21fq15gr47hsonmlkj字符字符5710332221364186频度频度ie edcba空格空格空格空格字符字符先建哈夫曼树，再利用此树对报文先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。进行编码和译码。要求编程实现：要求编程实现：80提示提示1 1：霍夫曼树中各结点的结构霍夫曼树中各结点的结构可以定义为如下可以定义为如下5 5个分量：个分量：charweight parentlchildRchild将整个将整个霍夫曼树的霍夫曼树的结点结点存储在一个数组中：存储在一个数组中：HT1.n;HT1.n;将结点的将结点的编码编码存储在存储在HC1.nHC1.n中。中。提示提示3 3：霍夫曼树如何构造？霍夫曼树如何构造？构造好之后又如何求得构造好之后又如何求得各结点对应的霍夫曼编码？各结点对应的霍夫曼编码？算法参见教材算法参见教材P147P147。提示提示2 2：霍夫曼树的霍夫曼树的存储结构存储结构可采用可采用顺序存储顺序存储结构：结构：实验二补充材料中的方案二程序；实验二补充材料中的方案二程序；喻信星空喻信星空FTPFTP网站上的网站上的“数据结构数据结构”演示程序演示程序参考参考参考参考资料资料资料资料81二叉树小结1 1、定义和性质、定义和性质2 2、存储结构、存储结构3 3、遍历、遍历4 4、线索化、线索化：线索树：线索树顺序结构顺序结构链式结构链式结构二叉链表二叉链表三叉链表三叉链表先序线索树先序线索树中序线索树中序线索树后序线索树后序线索树树二叉树二叉树森林中序遍历中序遍历后序遍历后序遍历先序遍历先序遍历霍夫曼树霍夫曼树霍夫曼编码霍夫曼编码82void iter_inorder(tree_pointer node)int top=-1;/*initialize stack*/tree_poi