《《数据结构789树》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构789树》PPT课件.ppt（70页珍藏版）》请在金锄头文库上搜索。
1、1 物料管理物料管理8/26/20241数据结构数据结构数据结构Data Structure彭宏京彭宏京南京工业大学计算机科学系南京工业大学计算机科学系南京工业大学计算机科学系南京工业大学计算机科学系2007200720072007年年年年9 9 9 9月月月月2 物料管理物料管理8/26/20242数据结构数据结构学时数学时数：48(32+16） 学学 分分： 3 教教 材：材：严蔚敏严蔚敏等，数据结构（等，数据结构（C语言版），清华大语言版），清华大学出版社，学出版社，1997年年4月月 （配题集配题集） 参考书：参考书：1 殷人昆等，殷人昆等，数据结构（用面向对象方法与数据结构（用面向对
2、象方法与C+描述），清华大学出版社，描述），清华大学出版社，1999年年7月。月。￥26 2 殷人昆等，殷人昆等，数据结构习题解析，清华大学出版数据结构习题解析，清华大学出版社，社，2002年年4月。月。￥263 李春葆，李春葆，数据结构习题与解析（数据结构习题与解析（C语言篇），清语言篇），清华大学出版社，华大学出版社，2001年年1月。月。￥284 丁宝康等，丁宝康等，数据结构自学考试指导，清华大学出数据结构自学考试指导，清华大学出版社，版社， 2001年年5月。月。￥233 物料管理物料管理8/26/20243数据结构数据结构内内 容容 安安 排排章内 容 学时 章 内 容 学时 1绪
3、论27图62线性表48动态存储管理略3栈和队列69查找44串（自学）210内部排序45数组和广义表（自学） 411外部排序略6树和二叉树 612文件略实验：课内上机（实验：课内上机（16规定内容）规定内容）+课外上机（课外上机（24平时作平时作业中编程题验证）业中编程题验证）4 物料管理物料管理8/26/20244数据结构数据结构数据结构课程的内容数据结构课程的内容各种数据各种数据结构的结构的应用应用5 物料管理物料管理8/26/20245数据结构数据结构1、树的定义和基本术语树的定义和基本术语2、二叉树二叉树3、遍历二叉树遍历二叉树和线索二叉树和线索二叉树4、树和森林树和森林5、树和等价问题
4、、树和等价问题6、赫夫曼树及其与树的应用赫夫曼树及其与树的应用7、回溯法与树的遍历、回溯法与树的遍历8、树的计数、树的计数目录目录第六章第六章 树和二叉树树和二叉树 特点：特点：非线性结构，一个直接前驱，但可能有多个非线性结构，一个直接前驱，但可能有多个直接后继。直接后继。 （一对多或（一对多或1:1:n n） 6 物料管理物料管理8/26/20246数据结构数据结构1、树的定义和基本术语、树的定义和基本术语（1 1）. . 树的定树的定树的定树的定义义义义注：注：树的定义具有树的定义具有递归性递归性，即，即“树中还有树树中还有树”。由一个或多个由一个或多个( (n0n0) )结点组成的有限集
5、合结点组成的有限集合T T，有且仅有有且仅有一一个结点称为根个结点称为根（rootroot），），当当n1n1时，其余的结点分为时，其余的结点分为m(m0)m(m0)个个互不相交互不相交的有限集合的有限集合T1,T2T1,T2，TmTm。每个集合本身又是棵每个集合本身又是棵树，被称作这个根的树，被称作这个根的子树子树 。（1）. 树的定义树的定义（2）.若干术语若干术语（3）.逻辑结构逻辑结构（4）.存储结构存储结构（5）.树的运算树的运算7 物料管理物料管理8/26/20247数据结构数据结构树的表示法主要有树的表示法主要有5种：种：v图形表示法图形表示法v嵌套集合表示法嵌套集合表示法v广义
6、表表示法广义表表示法v凹入表示法凹入表示法v左孩子右兄弟表示法左孩子右兄弟表示法1、树的定义和基本术语、树的定义和基本术语自学自学8 物料管理物料管理8/26/20248数据结构数据结构图形表示法：图形表示法：图形表示法：图形表示法：教师教师学生学生其他人员其他人员20042004级级 20052005级级 20062006级级20072007级级南工大信息学院南工大信息学院计算机系计算机系电子系电子系通信系通信系叶子叶子根根子树子树9 物料管理物料管理8/26/20249数据结构数据结构左孩子右兄弟表示法左孩子右兄弟表示法A AB BC CD DE EF FGGHHI IJ JKKL LMM
7、数据数据左孩子左孩子 右兄弟右兄弟10 物料管理物料管理8/26/202410数据结构数据结构（2 2）. . 若干术若干术若干术若干术语语语语即上层的那个结点即上层的那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点即以某结点为根的子树中的任一结点即以某结点为根的子树中的任一结点ABCGEIDHFJMLK 根根 叶子叶子 森林森林有序
8、树有序树无序树无序树即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集棵不相交的树的集合合(例如删除例如删除A后的子树个数后的子树个数)双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙结点各子树从左至右有序，不能互换（左为第一）结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。结点各子树可互换位置。11 物料管理物料管理8/26/202411数据结构数据结构（2）. 若干术语（续）若干术语（续）即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结
9、点树的度树的度树的深度树的深度(或高度或高度)ABCGEIDHFJMLK从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点（也称为内部结点）的结点（也称为内部结点）所有结点度中的最大值（所有结点度中的最大值（Max各结点的度各结点的度）指所有结点中最大的层数（指所有结点中最大的层数（Max各结点的层次各结点的层次）问：问：右上图中的结点数右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4（有几个直接后继就是几度，亦称（有几个直接后继就是几度，亦称“次数次数”）12 物料管理物料管理
10、8/26/202412数据结构数据结构ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点M的祖先是A、D、H13 物料管理物料管理8/26/202413数据结构数据结构（3 3）. . 树的逻辑结构树的逻辑结构树的逻辑结构树的逻辑结构 一对多（一对多（1:1:n n），），有多个直接后继（如家谱树、有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且目
11、录树等等），但只有一个根结点，且子树之间子树之间互不相交。互不相交。 （4 4）. . 树的存储结构树的存储结构树的存储结构树的存储结构 讨论讨论1：树是非线性结构，该怎样存储？树是非线性结构，该怎样存储？特点：特点：仍然有顺序存储、链式存储等方式。仍然有顺序存储、链式存储等方式。 理论上，理论上，你爱怎样存储就怎样存储（比如随手扔进存储器，就你爱怎样存储就怎样存储（比如随手扔进存储器，就像有些不爱收拾的同学对待自己的物品一样）！但如果这样的像有些不爱收拾的同学对待自己的物品一样）！但如果这样的话，你要取出来就很要命了（相信大家均有过找东西的烦恼）。话，你要取出来就很要命了（相信大家均有过找东
12、西的烦恼）。学数据结构就是让你学数据结构就是让你/计算机变得更有秩序和高效！计算机变得更有秩序和高效！原则是：原则是：物理存储要反映逻辑结构（逻辑关系必须在存储实现物理存储要反映逻辑结构（逻辑关系必须在存储实现时得到反映）时得到反映）!注：这两种存储方式对于线性结构来说很直观也很自然。注：这两种存储方式对于线性结构来说很直观也很自然。那么，这两种存储方式如何反映那么，这两种存储方式如何反映1:1:n n的树型关系呢？（的树型关系呢？（想一想一想？想？）14 物料管理物料管理8/26/202414数据结构数据结构二叉树二叉树二叉树二叉树讨论讨论3：树的树的链式存储链式存储方案应该怎样制定？方案应
13、该怎样制定？复原困难复原困难讨论讨论2：树的树的顺序存储顺序存储方案应该怎样制定？方案应该怎样制定？可用多重链表：可用多重链表：一个前趋指针，一个前趋指针，n n个后继指针。个后继指针。 细节问题：细节问题： 树中结点的结构类型样式该如何设计？树中结点的结构类型样式该如何设计？ 即应该设计成即应该设计成“等长等长”还是还是“不等长不等长”？ 缺点：缺点： 等长结构太浪费（每个结点的度不一定相同）；等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。不等长结构太复杂（要定义好多种结构类型）。先研究最简单、最有规律的树，然先研究最简单、最有规律的树，然后设法把一般
14、的树转化为简单树。后设法把一般的树转化为简单树。可规定为：可规定为： 从上至下、从左至右将树的结点依次存入内存。从上至下、从左至右将树的结点依次存入内存。重大缺陷：重大缺陷：解决思路：解决思路：不能唯一复原就没有实用价值！不能唯一复原就没有实用价值！其实你也可以来一个规定，但你的规定有用吗？其实你也可以来一个规定，但你的规定有用吗？如果有，那么恭喜你，呵呵！如果有，那么恭喜你，呵呵！15 物料管理物料管理8/26/202415数据结构数据结构（5 5）. . 树的运树的运树的运树的运算算算算 要明确：要明确：1. 普普通通树树（即即多多叉叉树树）若若不不转转化化为为二二叉叉树树，则则运运算很难
15、实现。算很难实现。2. 二二叉叉树树的的运运算算仍仍然然是是插插入入、删删除除、修修改改、查查找找、排排序序等等，但但这这些些操操作作必必须须建建立立在在对对树树结结点点能能够够“遍历遍历”的基础上！的基础上！本章重点：二叉树的本章重点：二叉树的表示和实现表示和实现遍历遍历遍历遍历指每个结点都被访问且仅访问一次，不遗漏不重复指每个结点都被访问且仅访问一次，不遗漏不重复指每个结点都被访问且仅访问一次，不遗漏不重复指每个结点都被访问且仅访问一次，不遗漏不重复“遍历遍历”实现了一实现了一种重要思想：种重要思想：非线性结构线性化非线性结构线性化16 物料管理物料管理8/26/202416数据结构数据结
16、构2、二叉树、二叉树为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “ “叉叉” ” 的树？的树？二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；所有树都能转为唯一对应的二叉树所有树都能转为唯一对应的二叉树（可以预习（可以预习6.46.4节）节）。（1）. 二叉树的定义二叉树的定义（2）. 二叉树的性质二叉树的性质（3）. 二叉树的二叉树的存存储结储结构构17 物料管理物料管理8/26/202417数据结构数据结构例：结点总数为例：结点总数为 3 时的所有二叉树的树时的所有二叉树的树的形状的形状 2、二叉树、二叉树（1）、二叉树的定义）、二叉树的定义是是n n
17、（n0n0）个结点的有限集合，由一个根结点以及两棵互不相交的分别称个结点的有限集合，由一个根结点以及两棵互不相交的分别称为为左子树和右子树左子树和右子树的二叉树组成。的二叉树组成。( (即即: :空或有一个根，根有左子树、右子空或有一个根，根有左子树、右子树；而左右子树本身又是二叉树。）树；而左右子树本身又是二叉树。）逻辑结构：逻辑结构： 一对二（一对二（1:21:2） 基本特征基本特征: : 每个结点最多只有两棵子树每个结点最多只有两棵子树 （不存在度大于（不存在度大于2 2的结点）；的结点）； 左子树和右子树左子树和右子树次序不能颠倒。次序不能颠倒。BCDEFL 例：二叉树例：二叉树 18
18、 物料管理物料管理8/26/202418数据结构数据结构2、二叉树、二叉树（2 2）、二叉树的性质：）、二叉树的性质：证：证：k = 1 时成立，设时成立，设 k = i-1 时成立时成立 则当则当 k = i 时时在二叉树的第在二叉树的第 i 层上层上至多有至多有 2 i-1-1 * 2 = 2 i-1 个结点个结点BCDEFLA1 1层：结点个数层：结点个数 2 21-11-1=2=20 0 个个2 2层：结点个数层：结点个数 2 22-12-1=2=21 1 个个3 3层：结点个数层：结点个数 2 23-13-1=2=22 2 个个性质性质1：在二叉树的第：在二叉树的第 i 层上至多有层
19、上至多有 2 i-1个结点个结点讨论讨论1 1：第：第i i层的结点数最多是多少？层的结点数最多是多少？ 2 2 2 2i-1i-1i-1i-1个个个个19 物料管理物料管理8/26/202419数据结构数据结构性质性质2 2：深度为：深度为 K K 的的二叉树至多有二叉树至多有2 2 k k- 1 - 1 个结点个结点证：利用性质证：利用性质 1 1 ，将第，将第 1 1 层至第层至第 k k 层的最多的结点数进行相加：层的最多的结点数进行相加：1 + 2 + 21 + 2 + 22 2 + + + 2 + 2k-2k-2 + 2 + 2k-1k-1 = 2 = 2k k - 1 - 1性质
20、性质3 3：二叉树的叶子结点数：二叉树的叶子结点数 n n0 0 等于度为等于度为 2 2 的结点数的结点数n n2 2 + 1 + 1 （即即n n0 0=n=n2 2+1+1） 证：证： 二叉树中全部结点数二叉树中全部结点数n nn n0 0+n+n1 1+n+n2 2( (叶子数叶子数1 1度结点数度结点数2 2度结点数度结点数) )又又又又二叉树中全部结点数二叉树中全部结点数n nB+1B+1 ( ( 总分支数根结点总分支数根结点 ) ) （除根结点外，每个结点必有一个直接前趋，即一个分支）（除根结点外，每个结点必有一个直接前趋，即一个分支）而而而而 总分支数总分支数B= nB= n1
21、 1+2n+2n2 2 (1(1度结点必有度结点必有1 1个直接后继，个直接后继，2 2度结点必有度结点必有2 2个个) )三式联立可得：三式联立可得：三式联立可得：三式联立可得： n n0 0+n+n1 1+n+n2 2= = n n1 1+2n+2n2 2 +1, +1, 即即n n0 0=n=n2 2+1+1讨论讨论2 2：深度为：深度为k k的二叉树，最多有多少个结点？的二叉树，最多有多少个结点？ 2 2 2 2k k k k-1-1-1-1个个个个讨论讨论3 3：二叉树的叶子数和度为：二叉树的叶子数和度为2 2的结点数之间有关系吗？的结点数之间有关系吗？20 物料管理物料管理8/26
22、/202420数据结构数据结构2. 2. 深度为的二叉树的结点总数，最多为深度为的二叉树的结点总数，最多为 个。个。 ) )k-1k-1 ) ) loglog2 2k k ) ) k k ) )k k1. 1. 树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的 。 ) ) 高度高度 ) ) 层次层次 ) ) 深度深度 ) ) 度度DCC3. 3. 深度为深度为9 9的二叉树中至少有的二叉树中至少有 个结点。个结点。 ) )9 9 ) )8 8 ) ) ) )9 91 1课堂练习：课堂练习：21 物料管理物料管理8/26/202421数据结构数据结构2、二叉树、二叉树BCDEFLAP
23、SQRUBCDEFLAPSQRXUWV满二叉树满二叉树:一棵深度为一棵深度为k 且有且有2k -1个结个结点的二叉树。点的二叉树。 特点：每层都特点：每层都“充满充满”了结了结点点完全二叉树完全二叉树:深度为深度为k 的的、有有n个个结点的二叉树，当且结点的二叉树，当且仅当其每一个结点都仅当其每一个结点都与深度为与深度为k 的满二叉的满二叉树中编号从树中编号从1至至n的结的结点一一对应。点一一对应。性质性质4 4：具有：具有 n n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 loglogloglog2 2 2 2n n n n 1 1 1 1 证：证：根据性质根据性质2 2，深度为
24、，深度为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-1n2n2k k 三边同时取对数，于是有：三边同时取对数，于是有：k-1logk-1log2 2nk n1，则其双亲是i/2(2) 如果2in，则结点i无左孩子；如果2in，则其左孩子是2i (3) 如果2i+1n，则结点i无右
25、孩子；如果2i+1n，则其右孩子是2i+1121110987654321为何要研究为何要研究这两种特殊这两种特殊形式？形式？因为只有这两种形式可因为只有这两种形式可以实现二叉树的顺序存以实现二叉树的顺序存储。储。23 物料管理物料管理8/26/202423数据结构数据结构问题问题问题问题: : : : 设一棵完全二叉树具有设一棵完全二叉树具有设一棵完全二叉树具有设一棵完全二叉树具有1000100010001000个结点，则它有个结点，则它有个结点，则它有个结点，则它有 个个个个叶子结点，有叶子结点，有叶子结点，有叶子结点，有 个度为个度为个度为个度为2 2 2 2的结点，有的结点，有的结点，有
26、的结点，有 个结点只有非空左个结点只有非空左个结点只有非空左个结点只有非空左子树，有子树，有子树，有子树，有 个结点只有非空右子树。个结点只有非空右子树。个结点只有非空右子树。个结点只有非空右子树。4894894894894884884884881 1 1 10 0 0 0由于最后一层叶子数为由于最后一层叶子数为由于最后一层叶子数为由于最后一层叶子数为489489489489个，是个，是个，是个，是奇数奇数奇数奇数，说明有，说明有，说明有，说明有1 1 1 1个结点只有非空个结点只有非空个结点只有非空个结点只有非空左子树；而完全二叉树中不可能出现非空右子树左子树；而完全二叉树中不可能出现非空右
27、子树左子树；而完全二叉树中不可能出现非空右子树左子树；而完全二叉树中不可能出现非空右子树(0(0(0(0个个个个) ) ) )。解：解：解：解：易求出总层数和末层叶子数。总层数易求出总层数和末层叶子数。总层数易求出总层数和末层叶子数。总层数易求出总层数和末层叶子数。总层数k=k=k=k= loglog2 2n n 1 1 = = = =10101010; ; ; ;且前且前且前且前9 9 9 9层总结点数为层总结点数为层总结点数为层总结点数为2 2 2 29 9 9 9-1=-1=-1=-1=511511511511 ( ( ( (完全二叉树的前完全二叉树的前完全二叉树的前完全二叉树的前k-1
28、k-1k-1k-1层肯定是满的层肯定是满的层肯定是满的层肯定是满的) ) ) )所以末层叶子数为所以末层叶子数为所以末层叶子数为所以末层叶子数为1000-511=1000-511=1000-511=1000-511=489489489489个。个。个。个。请注意叶子结点总数请注意叶子结点总数请注意叶子结点总数请注意叶子结点总数末层叶子数末层叶子数末层叶子数末层叶子数！还应当加上第还应当加上第还应当加上第还应当加上第k-1k-1k-1k-1层（靠右边）的层（靠右边）的层（靠右边）的层（靠右边）的0 0 0 0度结点个数。度结点个数。度结点个数。度结点个数。分析：分析：分析：分析：末层的末层的末层
29、的末层的489489489489个叶子只占据了上层的个叶子只占据了上层的个叶子只占据了上层的个叶子只占据了上层的245245245245个结点个结点个结点个结点（ 489/2489/2489/2489/2 ) ) ) )上层（上层（上层（上层（k=9)k=9)k=9)k=9)右边的右边的右边的右边的0 0 0 0度结点数还有度结点数还有度结点数还有度结点数还有2 2 2 29-19-19-19-1-245=-245=-245=-245=11111111个！个！个！个！ 第第第第i i i i层上的满层上的满层上的满层上的满结点数为结点数为结点数为结点数为2 2 2 2i-1i-1i-1i-1所
30、以，全部叶子数所以，全部叶子数所以，全部叶子数所以，全部叶子数489489489489( ( ( (末层末层末层末层) ) ) )11111111( ( ( (k-1k-1k-1k-1层层层层) ) ) )= = = =500500500500个。个。个。个。 度为度为度为度为2 2 2 2的结点的结点的结点的结点叶子总数叶子总数叶子总数叶子总数1=4991=4991=4991=499个。个。个。个。24 物料管理物料管理8/26/202424数据结构数据结构2、二叉树、二叉树（3）、二叉树的存储结构：）、二叉树的存储结构： 一、顺序存储结构一、顺序存储结构按按二二叉叉树树的的结结点点“自自上
31、上而而下下、从从左左至至右右”编编号号，用用一组连续的存储单元存储。一组连续的存储单元存储。A AB BC CD DE EF FG GH HI I123456789A AB BC CGGE EI ID DHHF F问：顺序存储后能否复原成唯一对应的二叉树形状？问：顺序存储后能否复原成唯一对应的二叉树形状？答：答：若是完全若是完全/ /满二叉树则可以做到唯一复原。满二叉树则可以做到唯一复原。 而且有规律：下标值为而且有规律：下标值为i i的双亲，其左孩子的下标值必为的双亲，其左孩子的下标值必为2 2i i，其右孩子的下标值必为其右孩子的下标值必为2 2i i1 1（即即性质性质5 5） 例如，对
32、应例如，对应22的两个孩子必为的两个孩子必为 44和和 5,5,即即B B的左孩子必的左孩子必是是D,D,右孩子必为右孩子必为E E。T0T0一一般不用般不用25 物料管理物料管理8/26/202425数据结构数据结构讨论：讨论：不是完全二叉树怎么办？不是完全二叉树怎么办？答：答：一律补全为完全二叉树！一律补全为完全二叉树！方法很简单，将各层空缺处统统补上方法很简单，将各层空缺处统统补上“虚结点虚结点”，其内容为空。，其内容为空。A AB B C C D D E E123456789.16ABECD缺点：缺点：浪费空间；浪费空间；插入、删除不便插入、删除不便 26 物料管理物料管理8/26/2
33、02426数据结构数据结构2、二叉树、二叉树(3)、二叉树的存储结构：、二叉树的存储结构：二、链式存储结构二、链式存储结构 仅定义结点的类型即可。仅定义结点的类型即可。ABCDEFGHILtypedef struct BiTNode TELemType data; struct BiTNode * lchild; struct BiTNode * rchild; BitTNode, * BiTree;BiTree p; data lchild rchild标准形式：（二叉链表）标准形式：（二叉链表）data lchild rchild parenttypedef struct BiTNode
34、TELemType data; struct BiTNode * lchild; struct BiTNode * rchild; struct BiTNode * parent; BitTNode, * BiTree;BiTree p; 广义标准形式：（三叉链表）广义标准形式：（三叉链表）如果需要倒查某结点的如果需要倒查某结点的双亲，可以再增加一个双亲，可以再增加一个双亲域（直接前趋）指双亲域（直接前趋）指针，将二叉链表变成三针，将二叉链表变成三叉链表。叉链表。用二叉链表即可方便表用二叉链表即可方便表示。一般从根结点开始示。一般从根结点开始存储。存储。（相应地，访问（相应地，访问树中结点时也
35、只能从根树中结点时也只能从根开始）开始）27 物料管理物料管理8/26/202427数据结构数据结构例：例： ABECDAB DCEdatadatalchildlchildrchildrchilddatadatalchildlchildrchildrchild28 物料管理物料管理8/26/202428数据结构数据结构ADEBCF rootlchild data rchild结点结构结点结构: 二叉链表二叉链表29 物料管理物料管理8/26/202429数据结构数据结构3、遍历二叉树和线索二叉树、遍历二叉树和线索二叉树一、遍历二叉树遍历二叉树遍历定义遍历定义遍历用途遍历用途遍历方法遍历方法指按
36、某条搜索路线遍访每个结点且不重复指按某条搜索路线遍访每个结点且不重复（又称周游）。（又称周游）。它是树结构插入、删除、修改、查找和排它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础序运算的前提，是二叉树一切运算的基础和核心。和核心。对每个结点的查看通常都是对每个结点的查看通常都是“先左后右先左后右” ” 。30 物料管理物料管理8/26/202430数据结构数据结构3、遍历二叉树和线索二叉树、遍历二叉树和线索二叉树遍历规则遍历规则v二叉树由根、左子树、右子树构成，定义为二叉树由根、左子树、右子树构成，定义为D、 L、R以根以根结点为参照系结点为参照系注：注：“先、中、后
37、先、中、后”的意思是指访问的结点的意思是指访问的结点D D是先于子树出是先于子树出现还是后于子树出现。现还是后于子树出现。v D、 L、R的组合定义了六种可能的遍历方案：的组合定义了六种可能的遍历方案： LDR, LRD, DLR, DRL, RDL, RLDv 若限定若限定先先左左后后右右，则有三种实现方案：，则有三种实现方案： DLR LDR LRD先先序遍历序遍历 中中序遍历序遍历 后后序遍历序遍历 31 物料管理物料管理8/26/202431数据结构数据结构3、遍历二叉树和线索二叉树、遍历二叉树和线索二叉树例例1：先序遍历的结果是：先序遍历的结果是：中序遍历的结果是：中序遍历的结果是：
38、后序遍历的结果是：后序遍历的结果是： A B CD ED B E D B E A A C CD E B C D E B C A A口诀：口诀：DLR先序遍历，即先序遍历，即先根再左再右先根再左再右LDR中序遍历，即先左再根再右中序遍历，即先左再根再右LRD后序遍历，即先左再右再根后序遍历，即先左再右再根A A B B D D E E C C32 物料管理物料管理8/26/202432数据结构数据结构+*A*/EDCB先序遍历结果先序遍历结果+ * * / A B C D E前缀表示法前缀表示法中序遍历结果中序遍历结果A / B * C * D + E中缀表示法中缀表示法后序遍历结果后序遍历结果
39、A B / C * D * E +后缀表示法后缀表示法层次遍历结果层次遍历结果+ * E * D / C A B例例2：用二叉树表示算术表达式用二叉树表示算术表达式33 物料管理物料管理8/26/202433数据结构数据结构中序遍历算法中序遍历算法中序遍历算法中序遍历算法LDR(node *root)if(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rchild); return(0);后序遍历算法后序遍历算法后序遍历算法后序遍历算法LRD (node *root)if(root !=NULL) LRD(roo
40、t-lchild); LRD(root-rchild); printf(“%d”,root-data); return(0);结点数据类型自定义结点数据类型自定义结点数据类型自定义结点数据类型自定义typedef struct nodeint data; struct node *lchild,*rchild； node;node *root; 先序遍历算法先序遍历算法先序遍历算法先序遍历算法DLR( node *root )if (root !=NULL) /非空二叉树非空二叉树 printf(“%d”,root-data); /访问访问D DDLR(root-lchild); /递递归归遍
41、遍历历左左子子树树DLR(root-rchild); /递递归归遍遍历历右右子子树树 return(0); 34 物料管理物料管理8/26/202434数据结构数据结构对遍历的分析：对遍历的分析：1. 从前面的三种遍历算法可以知道：如果将从前面的三种遍历算法可以知道：如果将print语句抹去，语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的遍历算法的访问路径是相同的，只是访问结点的时机不同访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径从虚线的出发点到终点的路径上，每个结点经过上，每个结点经过3次次
42、。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个辅助单元个辅助单元35 物料管理物料管理8/26/202435数据结构数据结构3、
43、遍历二叉树和线索二叉树、遍历二叉树和线索二叉树BCDELA(1)(1)、遍历二叉树：续、遍历二叉树：续先序的非递归实现：先序的非递归实现：1 1、根结点进栈根结点进栈2 2、结点出栈，被访问、结点出栈，被访问3 3、结点的右、左儿子（非空）进栈、结点的右、左儿子（非空）进栈4 4、反复执行、反复执行 2 2、3 3 ，至栈空为止。，至栈空为止。先序：先序：A、L、B、E、C、De.g:A出栈出栈访问访问L出栈访出栈访问问B出栈出栈访问访问E出栈出栈访问访问C出栈出栈访问访问D出栈访问出栈访问后，栈空结后，栈空结束束A进栈进栈C、L进栈进栈E、B进栈进栈D进栈进栈36 物料管理物料管理8/26/
44、202436数据结构数据结构3、遍历二叉树和线索二叉树、遍历二叉树和线索二叉树(1)、遍历二叉树：续、遍历二叉树：续中序的非递归实现：中序的非递归实现：1 1、结点（初始时是根结点）进栈，沿左指针查找左儿子。结点（初始时是根结点）进栈，沿左指针查找左儿子。2 2、若有左儿子，返回第一步。、若有左儿子，返回第一步。3 3、若无左儿子，判栈空？空则结束。非空，栈顶结点出栈、若无左儿子，判栈空？空则结束。非空，栈顶结点出栈 访问。转向右子树，返回访问。转向右子树，返回1 1。e.g:BCDELAXW中序：中序：B、L、E、 A、C、W、 X、Dinitstack(s);push(s,t); / t
45、是根结点是根结点while (!stackempty(s) while (Gettop(s,p) & p ) / 有值且非空时有值且非空时 push(s, p-lchild)； / null 值可能进栈值可能进栈 pop (s,p); / 空指针退栈空指针退栈 if (!stackempty(s) / 访问结点，向右一步访问结点，向右一步 pop(s, p); visit( p-data); push(s,p-rchild); 反复执行：向左走到尽头反复执行：向左走到尽头退栈访问退栈访问 转向右子树转向右子树37 物料管理物料管理8/26/202437数据结构数据结构3、遍历二叉树和线索二叉树
46、、遍历二叉树和线索二叉树(2)、线索二叉树、线索二叉树(自学自学)为什么采用线索二叉树：二叉树中的空指针场多达为什么采用线索二叉树：二叉树中的空指针场多达 n + 1 个。个。简单证明：设二叉树中结点的总数为简单证明：设二叉树中结点的总数为 n，度为度为 2 的结点总数为的结点总数为 n2 。空指针场用空指针场用方框代表。增加了方框结点的二叉树称之为扩展二叉树。在该二叉树之中，原来方框代表。增加了方框结点的二叉树称之为扩展二叉树。在该二叉树之中，原来的的 n 个结点全部成为度为个结点全部成为度为 2 的结点，方框结点成为叶子。根据二叉树的性质的结点，方框结点成为叶子。根据二叉树的性质 3 ，原
47、命题得证。原命题得证。e.g: n = 8 的二叉树的二叉树BCDELAXWBCDELAXW扩展二叉树扩展二叉树怎样利用这怎样利用这 n + 1 个空指针场？个空指针场？中序穿线树中序穿线树后序穿线树后序穿线树38 物料管理物料管理8/26/202438数据结构数据结构作业：作业：习题习题3本次课小结本次课小结1 1、掌握树和二叉树的基本概念，性质；、掌握树和二叉树的基本概念，性质；2 2、满二叉树和完全二叉树及其性质；、满二叉树和完全二叉树及其性质；3 3、二叉树的顺序存储是通过补全为完全二叉树，依、二叉树的顺序存储是通过补全为完全二叉树，依从上到下、从左到右的规定顺序来实现的；从上到下、从
48、左到右的规定顺序来实现的；4 4、二叉树的链式存储和线性表的链式存储一样，是、二叉树的链式存储和线性表的链式存储一样，是通过指向前驱和后继结点来实现，二叉链表较常用；通过指向前驱和后继结点来实现，二叉链表较常用；5 5、二叉树的遍历是其它操作和运算的基础，务必掌、二叉树的遍历是其它操作和运算的基础，务必掌握遍历二叉树的递归和非递归算法；握遍历二叉树的递归和非递归算法；6 6、下面的、下面的“遍历算法的应用举例遍历算法的应用举例遍历算法的应用举例遍历算法的应用举例”请认真消化。请认真消化。请认真消化。请认真消化。39 物料管理物料管理8/26/202439数据结构数据结构4、遍历算法的应用举例遍
49、历算法的应用举例( ( ( (稍加提示，同学们课后阅读稍加提示，同学们课后阅读稍加提示，同学们课后阅读稍加提示，同学们课后阅读) ) ) )(2)、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数(3)、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)(4)、复制二叉树、复制二叉树(后序遍历后序遍历)(5)(5)、建立二叉树的存储结构、建立二叉树的存储结构(1)、查询二叉树中某个结点、查询二叉树中某个结点40 物料管理物料管理8/26/202440数据结构数据结构1) 1) 在二叉树不空的前提下在二叉树不空的前提下, ,和根结点的元素进行比较和根结点的元素进行比较, ,若相等若相等,
50、,则找到返回则找到返回 TRUE;TRUE;2) 2) 否则在左子树中进行查找否则在左子树中进行查找, ,若找到若找到, , 则返回则返回 TRUE;TRUE;3) 3) 否则继续在右子树中进行查找否则继续在右子树中进行查找, ,若找到若找到, ,则返回则返回 TRUE,TRUE,否则返回否则返回 FALSE;FALSE;(1)(1)、查询二叉树中某个结点、查询二叉树中某个结点、查询二叉树中某个结点、查询二叉树中某个结点Status Preorder (BiTree T, ElemType x, BiTree &p) /若二叉树中存在和若二叉树中存在和 x 相同的元素，则相同的元素，则p p指
51、向该结点并返回指向该结点并返回OK, 否则返回否则返回 FALSE if (T) if (T-data=x) p = T; return OK, /if else return FALSE;else if (Preorder(T-lchild, x, p) return OK; else return(Preorder(T-rchild, x, p) ;/else41 物料管理物料管理8/26/202441数据结构数据结构(2)(2)(2)(2)、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数算法基本思想算法基本思想算法基本思想算
52、法基本思想: : : :先序先序先序先序( (或中序或后序或中序或后序或中序或后序或中序或后序) )遍历二叉树，在遍历过程中查找叶子结点，遍历二叉树，在遍历过程中查找叶子结点，遍历二叉树，在遍历过程中查找叶子结点，遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个并计数。由此，需在遍历算法中增添一个并计数。由此，需在遍历算法中增添一个并计数。由此，需在遍历算法中增添一个“ “计数计数计数计数” ”的参数，并将算法中的参数，并将算法中的参数，并将算法中的参数，并将算法中“ “访问结访问结访问结访问结点点点点” ” 的操作改为的操作改为的操作改为的操作改为: :若是叶子，则
53、计数器增若是叶子，则计数器增若是叶子，则计数器增若是叶子，则计数器增1 1。void CountLeaf (BiTree T, int& count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeafint CountLeaf (BiTree T) /返回指针T所指二叉树中所有叶子结点个数 if (!T ) return 0; if (!T-lchild & !T-rchild) ret
54、urn 1; else m = CountLeaf( T-lchild); n = CountLeaf( T-rchild); return (m+n); /else / CountLeaf42 物料管理物料管理8/26/202442数据结构数据结构(3)(3)、求二叉树的深度、求二叉树的深度( (后序遍历后序遍历) )算法基本思想算法基本思想: :首先分析二叉树的深度二叉树的深度和它的左左、右子树深度右子树深度之间的关系。 从二叉树深度的定义可知，二叉树的深度应为其左、右子树深二叉树的深度应为其左、右子树深度的最大值加度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右
55、子树的深度，算法中访问结点的操作为:求得左、右子树深度的最大值，然后加求得左、右子树深度的最大值，然后加1 1 。int Depth (BiTree T ) / 返回二叉树的深度 if (!T) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1+(depthLeftdepthRight?depthLeft:depthRight); return depthval;void void DepthDepth( (BiTreeBiTree T , T , inti
56、nt level, level, intint & &dvaldval) ) if ( T ) if ( T ) if (level if (leveldvaldval) ) dvaldval = level; = level; DepthDepth( T-( T-lchildlchild, level+1, , level+1, dvaldval ); ); DepthDepth( T-( T-rchildrchild, level+1, , level+1, dvaldval ); ); / /调用之前调用之前调用之前调用之前 level level 的初值为的初值为的初值为的初值为 1,
57、 1, dvaldval 的初值为的初值为的初值为的初值为 0. 0.43 物料管理物料管理8/26/202443数据结构数据结构(4)(4)(4)(4)、复制二叉树、复制二叉树、复制二叉树、复制二叉树( ( ( (后序遍历后序遍历后序遍历后序遍历) ) ) )其基本操作为其基本操作为其基本操作为其基本操作为: : : :生成一个结点。生成一个结点。生成一个结点。生成一个结点。根元素根元素根元素根元素NEWTNEWT左子树左子树左子树左子树右子树右子树右子树右子树根元素根元素根元素根元素TT左子树左子树左子树左子树右子树右子树右子树右子树左子树左子树左子树左子树右子树右子树右子树右子树A AB
58、 BC CD DE EF FGGHHKK D D C C H H K K G G A AnewTnewTnewT F F B B E E 44 物料管理物料管理8/26/202444数据结构数据结构BiTNodeBiTNode * *GetTreeNodeGetTreeNode( (TElemTypeTElemType item, item, BiTNodeBiTNode * *lptrlptr , , BiTNodeBiTNode * *rptrrptr ) ) if (!(T = new if (!(T = new BiTNodeBiTNode) exit(1);) exit(1); T-
59、 data = item; T- T- data = item; T- lchildlchild = = lptrlptr; T- ; T- rchildrchild = = rptrrptr; ; return T; return T; 生成一个二叉树的结点生成一个二叉树的结点(其数据域为其数据域为item,左指针域为左指针域为lptr,右指针域为右指针域为rptr)BiTNodeBiTNode * *CopyTreeCopyTree( (BiTNodeBiTNode *T) *T) if (!T) return NULL; if (!T) return NULL; if (T- if (T
60、-lchildlchild ) ) newlptrnewlptr = = CopyTreeCopyTree(T-(T-lchildlchild); ); / /复制左子树复制左子树复制左子树复制左子树 else else newlptrnewlptr = NULL; = NULL; if (T- if (T-rchildrchild ) ) newrptrnewrptr = = CopyTreeCopyTree(T-(T-rchildrchild); ); / /复制右子树复制右子树复制右子树复制右子树 else else newrptrnewrptr = NULL; = NULL; newT
61、newT = = GetTreeNodeGetTreeNode(T-data, (T-data, newlptrnewlptr, , newrptrnewrptr); ); return return newTnewT; ; / / CopyTreeCopyTree45 物料管理物料管理8/26/202445数据结构数据结构(5)(5)(5)(5)、建立二叉树的存储结构、建立二叉树的存储结构、建立二叉树的存储结构、建立二叉树的存储结构用用空格字符表示空格字符表示无孩子无孩子或指针或指针为空为空注：注：要实现遍历运算，必须先把二叉树存入电脑内要实现遍历运算，必须先把二叉树存入电脑内怎样建树？见怎
62、样建树？见教材教材P131P131例例例：将下面的二叉树以二叉链表形式例：将下面的二叉树以二叉链表形式存入计算机内。存入计算机内。A AB BGGD DF FC CE E考虑考虑1 1：输入结点时怎样表示输入结点时怎样表示“无孩子无孩子”？考虑考虑2 2：以何种遍历方式来输入和建树？以何种遍历方式来输入和建树？将二叉树按先序遍历次序输入：将二叉树按先序遍历次序输入：A B C D E G F 以先序遍历最为合以先序遍历最为合适，让每个结点都适，让每个结点都能及时被连接到位能及时被连接到位。46 物料管理物料管理8/26/202446数据结构数据结构建树算法：建树算法：Status Create
63、BiTree( BiTree &T ) /构造二叉树构造二叉树T Tscanf(“%c”,&ch);if(ch=)T=NULL; else if(!(T=( BiTNode*)malloc(sizeof(BiTNode)exit(overflow); T-data=ch; /生成根结点生成根结点 CreateBiTree(T-lchild); /构造左子树构造左子树 CreateBiTree(T-rchild); /构造右子树构造右子树 return OK; /CreateBiTree输入序列：输入序列： A B C D E G F 47 物料管理物料管理8/26/202447数据结构数据结构
64、上次课回顾和本次课内容提示上次课回顾和本次课内容提示:本本章（树和二叉树）第二次授课章（树和二叉树）第二次授课已经弄清和解决二叉树的存储，及其重要的遍历运算。请已经弄清和解决二叉树的存储，及其重要的遍历运算。请同学们继续：同学们继续：1 1、设法理清楚解决二叉树的存储问题的基本思路；和线性、设法理清楚解决二叉树的存储问题的基本思路；和线性结构相比，它有什么特点；结构相比，它有什么特点；2 2、完全二叉树的特点和性质为我们实现普通二叉树的顺序、完全二叉树的特点和性质为我们实现普通二叉树的顺序存储提供了什么启示和帮助，该顺序存储有什么缺陷？存储提供了什么启示和帮助，该顺序存储有什么缺陷？3 3、二
65、叉树的递归性定义，使得二叉树的递归性定义，使得“遍历遍历”运算很容易实现；运算很容易实现；充分理解使用堆栈实现充分理解使用堆栈实现“遍历遍历”的非递归算法；的非递归算法；本次课主要解决本次课主要解决1、一般树的存储问题和、一般树的存储问题和“遍历遍历”运算的实现运算的实现（只要掌握了树（只要掌握了树转化为二叉树的方法，那么上述问题就是直接的）转化为二叉树的方法，那么上述问题就是直接的）；2、重点介绍赫夫曼的构造及其应用。、重点介绍赫夫曼的构造及其应用。48 物料管理物料管理8/26/202448数据结构数据结构4、树和森林、树和森林1、树的存储结构、树的存储结构标准形式：树中的每个结点除有数据
66、场之外，还有标准形式：树中的每个结点除有数据场之外，还有 K 个指针场；其中个指针场；其中 K 为树的度数。为树的度数。1、数据场数据场第一个儿子结第一个儿子结点的地址点的地址第二个儿子结第二个儿子结点的地址点的地址第第 K 个儿子个儿子结点的地址结点的地址父亲结点的地父亲结点的地址址广义标准形式：在标准形式的基础上，再增加指向父亲结点的指针场。广义标准形式：在标准形式的基础上，再增加指向父亲结点的指针场。 E.g: 度数度数 K 3 的树的树ABCDEFGHILA 1 2 3 -1B 9 4 -1 0C 5 -1 -1 0D 6 7 -1 0E -1 -1 -1 1F -1 -1 -1 2G
67、 8 -1 -1 3H -1 -1 -1 3I -1 -1 -1 6P -1 -1 -1 -1 0123456789-1 表示空表示空缺点：空指针场太多，多达缺点：空指针场太多，多达 ( K -1 ) n + 1 个。个。改进：结点中设立度数场，改进：结点中设立度数场， 指针场依度数定。但指针场依度数定。但 操作麻烦。操作麻烦。 采用左儿子、兄弟表采用左儿子、兄弟表 示法。示法。用数组表用数组表示左图的示左图的树树 49 物料管理物料管理8/26/202449数据结构数据结构4、树和森林、树和森林1、树的存储结构、树的存储结构左儿子、兄弟表示法：树中的每个结点有数据场、指向它的第一棵子树树根的
68、指针场、左儿子、兄弟表示法：树中的每个结点有数据场、指向它的第一棵子树树根的指针场、指向它的兄弟结点的指针场。指向它的兄弟结点的指针场。实质上是用二叉树表示一棵树。实质上是用二叉树表示一棵树。数据场数据场第一棵子树根第一棵子树根结点的地址结点的地址下一个亲兄弟下一个亲兄弟结点的地址结点的地址 E.g: 度数度数 K 3 的树的树ABCDEFGHIL A B C D E F G H L I 50 物料管理物料管理8/26/202450数据结构数据结构4、树和森林、树和森林2、树、森林于二叉树的转换、树、森林于二叉树的转换树转换成相对应的二叉树：树转换成相对应的二叉树：1、保留每个结点的最左面的分
69、支，其余分支都被删除。、保留每个结点的最左面的分支，其余分支都被删除。2、同一父结点下面的结点成为它的左方结点的兄弟。、同一父结点下面的结点成为它的左方结点的兄弟。 E.g: 度数度数 K 3 的树的树ABCDEFGHILABCDEFGHILABCDEFGHIL51 物料管理物料管理8/26/202451数据结构数据结构4、树和森林、树和森林2、树、森林于二叉树的转换、树、森林于二叉树的转换森林转换成相对应的二叉树：森林转换成相对应的二叉树：增加一个虚拟的根结点，它的儿子为各棵树的根。增加一个虚拟的根结点，它的儿子为各棵树的根。那么，就变成了树转换成二叉树的问题。那么，就变成了树转换成二叉树的
70、问题。 E.g: 3 棵分别以棵分别以B、 C、D为根的树为根的树BCDEFGHILBCDEFGHILABCDEFGHILA 相应的二叉树相应的二叉树52 物料管理物料管理8/26/202452数据结构数据结构4、树和森林、树和森林2、树、森林于二叉树的转换、树、森林于二叉树的转换森林转换成相对应的二叉树：森林转换成相对应的二叉树：增加一个虚拟的根结点，它的儿子为各棵树的根。增加一个虚拟的根结点，它的儿子为各棵树的根。那么，就变成了树转换成二叉树的问题。那么，就变成了树转换成二叉树的问题。 E.g: 3 棵分别以棵分别以B、 C、D为根的树为根的树BCDEFGHILBCDEFGHILABCDE
71、FGHIL 相应的二叉树相应的二叉树53 物料管理物料管理8/26/202453数据结构数据结构树与二叉树转换树与二叉树转换ACBED树ABCDE二叉树 A B C D E A B C D E A B C D E 对应存储存储解释解释54 物料管理物料管理8/26/202454数据结构数据结构u将树转换成二叉树将树转换成二叉树加线：在兄弟之间加一连线加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转旋转：以树的根结点为轴心，将整树顺时针转45ABCDEFGHIA
72、BCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空55 物料管理物料管理8/26/202455数据结构数据结构u将将二叉二叉树转换成树树转换成树加线：若加线：若p结点是双亲结点的左孩子，则将结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与沿分支找到的所有右孩子，都与p的双亲用线连起来的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGH
73、IABCDEFGHIABCDEFGHIABCDEFGHI56 物料管理物料管理8/26/202456数据结构数据结构u森林转换成二叉树森林转换成二叉树将各棵树分别转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ57 物料管理物料管理8/26/202457数据结构数据结构u二叉树转换成森林二叉树转换成森林抹线：将二叉树中根结点与其右
74、孩子连线，及沿右分支搜索到的所有右孩子抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ58 物料管理物料管理8/26/202458数据结构数据结构4、树和森林、树和森林3、树、森林的遍历、树、森林的遍历树的前序、后序遍历：树的前序、后序遍历：1、类似于二叉树的前序遍历：、类似于二叉树的前序遍历：NLR；N:根；根；L：左子树（第一棵子树），左子树（第一棵子树）， R：其余
75、的那些子树，遍历方向由第二棵子树至最后一棵子树其余的那些子树，遍历方向由第二棵子树至最后一棵子树2、类似于二叉树的后序遍历：、类似于二叉树的后序遍历：LRN：L：左子树（第一棵子树），左子树（第一棵子树），R：其其 余的那些子树，遍历方向由第二棵子树至最后一棵子树，余的那些子树，遍历方向由第二棵子树至最后一棵子树， N:根根NBCDEFGHILA T1 T2 T3LR前序：前序：A、B、L、E、C、F、D、G、I、H后序：后序：L、E、B、F、C、I、G、H、D、A59 物料管理物料管理8/26/202459数据结构数据结构4、树和森林、树和森林3、树、森林的遍历、树、森林的遍历森林的前序、中
76、序遍历：森林的前序、中序遍历：前序遍历类似于树的前序遍历。增加一个虚拟的根结点，它的儿子为各棵树的前序遍历类似于树的前序遍历。增加一个虚拟的根结点，它的儿子为各棵树的根。那么对这棵树进行前序遍历，即得到森林的前序序列（不含树根结点）根。那么对这棵树进行前序遍历，即得到森林的前序序列（不含树根结点）后序遍历类似于树的后序遍历。增加一个虚拟的根结点，它的儿子为各棵树的后序遍历类似于树的后序遍历。增加一个虚拟的根结点，它的儿子为各棵树的根。那么对这棵树进行后序遍历，即得到森林的后序序列（去掉树根结点）根。那么对这棵树进行后序遍历，即得到森林的后序序列（去掉树根结点） 注意：本书称之为注意：本书称之为
77、中序遍历中序遍历, 如称之为后序遍历更合理。如称之为后序遍历更合理。前序：前序：B、L、E、C、F、D、G、I、H中序：中序：L、E、B、F、C、I、G、H、DBCDEFGHILABCDEFGHIL60 物料管理物料管理8/26/202460数据结构数据结构4、树和森林、树和森林3、树、森林的遍历、树、森林的遍历树的前序、后序遍历序列和相应的二叉树的前序、中序遍历序列一一对应：树的前序、后序遍历序列和相应的二叉树的前序、中序遍历序列一一对应：前序序列和对应的二叉树的前序序列完全一致。前序序列和对应的二叉树的前序序列完全一致。E、G：左图的树的根左图的树的根 A，及它的儿子结点及它的儿子结点 B
78、、C、D 在树的在树的 的前序序列和相应的二叉树中前序序列中的序号。的前序序列和相应的二叉树中前序序列中的序号。 根根 A: 11 结点结点 B： 22 结点结点 C： 55 结点结点 D： 77BCDEFGHILAABCDEFGHIL以以 C 为例：为例：在树中：在树中： 序号序号 根节点数根节点数 第一棵子第一棵子树的结点数树的结点数 1 5在二叉树中：在二叉树中： 序号序号 根节点数根节点数 左儿子数左儿子数左儿子子树结点数左儿子子树结点数 1 561 物料管理物料管理8/26/202461数据结构数据结构4、树和森林、树和森林3、树、森林的遍历、树、森林的遍历树的前序、后序遍历序列和相
79、应的二叉树的前序、中序遍历序列一一对应：树的前序、后序遍历序列和相应的二叉树的前序、中序遍历序列一一对应：后序序列和对应的二叉树的中序序列完全一致。后序序列和对应的二叉树的中序序列完全一致。E、G：左图的树的根左图的树的根 A，及它的儿子结点及它的儿子结点 B、C、D 在树的在树的 的后序序列和相应的二叉树的中序序列中的序号。的后序序列和相应的二叉树的中序序列中的序号。 根根 A: 1010 结点结点 B： 33 结点结点 C： 55 结点结点 D： 99BCDEFGHILAABCDEFGHIL后序：后序：L、E、B、F、C、I、G、H、D、A以以 C 为例：为例：在树中：在树中： 序号序号
80、第一棵子树的结点数第一棵子树的结点数 C 的子树的结点数的子树的结点数 1 5在二叉树中：在二叉树中： 序号序号 B 的左子树的结点数的左子树的结点数 B 的结点数的结点数 C 的左子树结点数的左子树结点数 1 5中序：中序：L、E、B、F、C、I、G、H、D、A62 物料管理物料管理8/26/202462数据结构数据结构4、树和森林、树和森林3、树、森林的遍历、树、森林的遍历森林的前序、中序（当作后序更好理解）和相应的二叉树的前序、中序遍历序列一一对应森林的前序、中序（当作后序更好理解）和相应的二叉树的前序、中序遍历序列一一对应 E.g: 3 棵分别以棵分别以B、 C、D为根的树为根的树BC
81、DEFGHILBCDEFGHILABCDEFGHILA 相应的二叉树相应的二叉树63 物料管理物料管理8/26/202463数据结构数据结构6、赫夫曼树及其应用、赫夫曼树及其应用1、最优二叉树（赫夫曼树）、最优二叉树（赫夫曼树） 路径长度：结点之间的树枝的总数路径长度：结点之间的树枝的总数树的路径长度：从根到每一结点的路径长度之和树的路径长度：从根到每一结点的路径长度之和树的带权路径长度：树的带权路径长度：叶子叶子结点的带权路径长度之和。设有结点的带权路径长度之和。设有 n 片叶子，它们的权值分别片叶子，它们的权值分别 为为 w1、w2、.wn， 相应的路径长度分别为相应的路径长度分别为 L1
82、、L2、.Ln。 则树的带权路径长度可记为：则树的带权路径长度可记为： nWPL = wklk k=1EGHLLEHGEGHL777524442255WPL=36WPL=46WPL=35最优二叉树或赫夫曼树：树的带权路径长度最优二叉树或赫夫曼树：树的带权路径长度 WPL 最小的二叉树。最小的二叉树。64 物料管理物料管理8/26/202464数据结构数据结构6、赫夫曼树及其应用、赫夫曼树及其应用1、最优二叉树（赫夫曼树）、最优二叉树（赫夫曼树） 赫夫曼算法（产生最优二叉树的算法）的实现：赫夫曼算法（产生最优二叉树的算法）的实现：1、给定一个具有给定一个具有 n 个权值个权值 w1,w2,wn
83、的结点的集合的结点的集合 F = T1,T2,Tn 。2、初始时，设初始时，设 A F。3、执行执行 i = 1 至至 n-1 次循环，在每次循环时，做以下事情：次循环，在每次循环时，做以下事情：从当前集合中选取权值最小、次最小的两个结点，以从当前集合中选取权值最小、次最小的两个结点，以 这两个结点作为内部结这两个结点作为内部结 点点 bi 的左右儿子，的左右儿子，bi 的权值为其左右儿子权值之和。在集合中删除这两个权的权值为其左右儿子权值之和。在集合中删除这两个权 值最小、次最小的结点。这样，在集合值最小、次最小的结点。这样，在集合 A 中，结点个数便减少了一个。中，结点个数便减少了一个。
84、e.g: 权值（此处为使用概率）分别为权值（此处为使用概率）分别为 2, 7, 4, 5 的结点集合的结点集合 F C, A, S, T 已知。已知。 请利用赫夫曼算法产生最优二叉树。请利用赫夫曼算法产生最优二叉树。C, 2A, 7S, 4T, 51、A=b1,6A, 7T, 5S, 4C, 22、A=b1,6A, 7S, 4C, 2b2,11 T, 53、A=b3,184、A=65 物料管理物料管理8/26/202465数据结构数据结构6、赫夫曼树及其应用、赫夫曼树及其应用2、赫夫曼编码、赫夫曼编码 赫夫曼算法用于通信中的字符的编码。将权值当着使用概率。赫夫曼树的左分支赫夫曼算法用于通信中的
85、字符的编码。将权值当着使用概率。赫夫曼树的左分支 标记为标记为 1，而右分枝标记为，而右分枝标记为 0；这从根到每一个叶子结点（字符）的路经上标记的字符组成的字；这从根到每一个叶子结点（字符）的路经上标记的字符组成的字 符串，即为该字符的赫夫曼编码。符串，即为该字符的赫夫曼编码。 e.g: 权值（此处为使用概率）分别为权值（此处为使用概率）分别为 2, 7, 4, 5 的结点集合的结点集合 F C, A, S, T 已知。已知。 请利用赫夫曼算法产生最优二叉树。请利用赫夫曼算法产生最优二叉树。b1,6A, 7S, 4C, 2b2,11T, 5b3,18111000赫夫曼编码：赫夫曼编码：A：0
86、T：10C：110S ：111赫夫曼编码优点：赫夫曼编码优点： 占用二进制位少占用二进制位少e.g: 左图发送长度为左图发送长度为 n 的字符串，等长表示需的字符串，等长表示需 2n 个比特。因共有四个字符，表示每个字符需个比特。因共有四个字符，表示每个字符需 二个二个 比特。比特。 采用赫夫曼编码后，总的比特数采用赫夫曼编码后，总的比特数 35n/18, 因：因： A：1*7n /18 T： 2*5n /18 S： 3*4n /18 C：3*2n /18 66 物料管理物料管理8/26/202466数据结构数据结构6、赫夫曼树及其应用、赫夫曼树及其应用2、赫夫曼编码、赫夫曼编码 赫夫曼算法的
87、实现：赫夫曼算法的实现：1、建立具有、建立具有 2n-1 个单元的数组，个单元的数组，其中其中 n 个单元用于保存初始结点，个单元用于保存初始结点，n-1 个结点用于表示内部结点。个结点用于表示内部结点。2、执行、执行 n-1 次循环，每次产生一个次循环，每次产生一个内部结点。权值最小的两个结点为其内部结点。权值最小的两个结点为其左右儿子。左右儿子。3、计算每个字符的赫夫曼编码。、计算每个字符的赫夫曼编码。b1,6A, 7S, 4C, 2b2,11T, 5b3,18111000数据结构：数据结构： typedef struct unsigned int weight ; unsigned in
88、t parent, lchild, rchild ; HTNode, * HuffmanTree: typedef char * * hufmanCode ;67 物料管理物料管理8/26/202467数据结构数据结构6、赫夫曼树及其应用、赫夫曼树及其应用2、赫夫曼编码、赫夫曼编码 赫夫曼算法的程序实现赫夫曼算法的程序实现b1,6A, 7S, 4C, 2b2,11T, 5b3,18111000Void hufmanCode ( HufumanTree &HT, HumanCode &HC, int *w, int n )if ( n = 1 ) return; m = 2 * n -1;HT
89、= ( HuffmanTree ) malloc ( m + 1) * sizeof ( HTNode ); / 不用不用 0 号单元号单元for ( p = HT, i = 1, p+; i = n; +i, +p, +w ) *p = *w, 0, 0, 0 ; / 书上漏书上漏 p+for ( ; i = m; +i, +p ) *p = 0, 0, 0, 0 ;for ( i = n +1; i = m; +i ) Select ( HT, i -1, s1, s2 ) ; / 可以用堆或优先队列，使时间降低到可以用堆或优先队列，使时间降低到 O（logn） HTs1.parent =
90、 i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2 ; HTi. Weight = HTs1. weight + HTs2. 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
91、= f, f = HT f .parent ) if ( HT f .lchild = c ) cd - - start = ” 0” ；else cd - - start =“ 1” ; HCi = ( char * ) malloc ( n - start ) * sizeof ( char * ); strcpy(HCi, &cdstart); free(cd);0 1 n n+1 n+2 2n-1 注意： Select 子程序不考虑父结点地子程序不考虑父结点地 址不为址不为 0 的结点的结点,范围：范围：1i-10 1 2 n-2 n-1cd 字符数组字符数组 68 物料管理物料管理8
92、/26/202468数据结构数据结构作业作业习题习题369 物料管理物料管理8/26/202469数据结构数据结构本章小结本章小结本章小结本章小结1 1、定义和性质定义和性质2 2、存储结构存储结构3 3、遍历遍历4 4、线索化线索化：线索树：线索树顺序结构顺序结构链式结构链式结构二叉链表二叉链表三叉链表三叉链表先序线索树先序线索树中序线索树中序线索树后序线索树后序线索树树树树树二叉树二叉树二叉树二叉树森林森林森林森林先先序序遍遍历历后后序序遍遍历历遍历遍历存储结构存储结构遍历遍历双亲表示双亲表示孩子表示孩子表示孩子兄弟孩子兄弟先序遍历先序遍历后序遍历后序遍历中序遍历中序遍历后序遍历后序遍历先
93、序遍历先序遍历霍夫曼树霍夫曼树霍夫曼编码霍夫曼编码70 物料管理物料管理8/26/202470数据结构数据结构1.熟练掌握二叉树的结构特性二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构存储结构的特点及适用范围。3.遍历二叉树遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归递归算法算法，灵活运用遍历算法灵活运用遍历算法实现二叉树的其它操作。层次遍历层次遍历是按另一种搜索策略进行的遍历。4.熟悉树的树的各种存储结构存储结构及其特点，掌握树和森林与二叉树的树和森林与二叉树的转换转换方法。建立存储结构是进行其它操作的前提，应掌握掌握 1 至 2 种建立建立二叉树和树的存储结构的方法存储结构的方法。5.学会编写实现树的各种操作实现树的各种操作的算法。6.了解最优树的特性最优树的特性，掌握建立建立最优树和哈夫曼编码最优树和哈夫曼编码的方法
