数据结构第六章数和二叉树

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. 树的定义树的定义注注1：过去许多书籍中都定义树

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

3、示法有几种：树的表示法有几种：图形表示法图形表示法嵌套集合表示法嵌套集合表示法广义表表示法广义表表示法目录表示法目录表示法左孩子右兄弟表示法左孩子右兄弟表示法这些表示法的示意图这些表示法的示意图参见教材参见教材p120p120树的抽象数据类型定义树的抽象数据类型定义参参见教材见教材p118-119p118-1196图形表示法：图形表示法：教师教师学生学生其他人员其他人员20032003级级 20042004级级 20052005级级20062006级级河南大学河南大学物理系物理系计算机系计算机系化学系化学系叶子叶子根根子树子树7嵌套集合表示法嵌套集合表示法( a ( b ( e ( k, l

4、), f ), c ( g ), d ( h ( m ), i, j ) ) 根作为根作为由子树森林组成的由子树森林组成的表的名字写在表的左边表的名字写在表的左边(a(b(e(f),g),c,d(h(i),j,k(l) (c) 广义表表示法a bdjcklhiefg(a) 嵌套集合表示法 a b e f g c d h i j k l( b) 凹入表示法8左孩子右兄弟表示法左孩子右兄弟表示法数据数据左孩子左孩子 右兄弟右兄弟( a ( b ( e ( k, l ), f ), c ( g ), d ( h ( m ), i, j ) ) )9 树的抽象数据类型定义树的抽象数据类型定义adt t

5、ree数据对象数据对象d:数据关系数据关系r:基本操作基本操作 p：adt tree若若d为空集，则称为空树；为空集，则称为空树；/允许允许n=0若若d中仅含一个数据元素，则中仅含一个数据元素，则r为空集；为空集；其他情况下的其他情况下的r存在二元关系：存在二元关系： root 唯一唯一 /关于根的说明关于根的说明 djdk= /关于子树不相交的说明关于子树不相交的说明 hj hk= 且且hi仍然是一棵树仍然是一棵树 /关于数据元素的说明关于数据元素的说明d是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有15个个abcgeidhfjmlk102. 若干术语若干术语

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

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

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

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

10、后继指针。个后继指针。细节问题：细节问题：树中结点的结构类型样式该如何设计？树中结点的结构类型样式该如何设计？ 即应该设计成即应该设计成“等长等长”还是还是“不等长不等长”？缺点：缺点：等长结构太浪费（每个结点的度不一定相同）；等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。不等长结构太复杂（要定义好多种结构类型）。解决思路：解决思路：先研究最简单、最有规律的树，然后设法把先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。一般的树转化为简单树。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层上至多有层上至多有个结点（个结点（i i00）。）。性质性质2: 2: 深度为深度为k k的二叉树至多有的二叉树至多有个结点（个结点（k0k0）。）。2 2i-1i-1个个提问：第提问：第i i层上至少有层上至少有 个结点？个结点？1 1讨论讨论2 2：深度为：深度为k k的二叉树，至多

15、有多少个结点？的二叉树，至多有多少个结点？ （利用二进制性质可轻松求出）（利用二进制性质可轻松求出）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度结点数度结点数

16、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满二叉树：满二叉树：一棵深度为一棵深度为k 且有且有2k -1个结点的二叉树。个结点的二叉树。

17、（特点：每层都（特点：每层都“充满充满”了结点）了结点）完全二叉树：完全二叉树：深度为深度为k 的的，有有n个结点个结点的二叉树，当且仅当其每一个结点都与的二叉树，当且仅当其每一个结点都与深度为深度为k 的满二叉树中编号从的满二叉树中编号从1至至n的结的结点一一对应。点一一对应。aobcgekdjfihnml深度为深度为4 4的满二叉树的满二叉树深度为深度为4 4的的完全二叉树完全二叉树abcgeidhfj为何要研究这两种特殊形式？为何要研究这两种特殊形式？因为它们在顺序存储方式下可以复原！因为它们在顺序存储方式下可以复原！ 完全二叉树的特点就是，只有最后一层完全二叉树的特点就是，只有最后一层

18、叶子不满，且全部集中在左边。叶子不满，且全部集中在左边。 这其实是这其实是的含义。在的含义。在的的“完全二叉树完全二叉树”是指是指n1=0的情况。的情况。21对于两种特殊形式的二叉树（对于两种特殊形式的二叉树（满二叉树和完全二叉树满二叉树和完全二叉树），还特别具备以下），还特别具备以下2 2个性质：个性质：2log1n 性质性质4: 4: 具有具有n n个结点的完全二叉树的深度必为个结点的完全二叉树的深度必为性质性质5: 5: 对完全二叉树，若从上至下、从左至右编号，则对完全二叉树，若从上至下、从左至右编号，则编号为编号为i 的结点，其左孩子编号必为的结点，其左孩子编号必为2i，其右孩子编号必

19、，其右孩子编号必为为2i1；其双亲的编号必为；其双亲的编号必为i/2（i1 时为根时为根, ,除外除外）。）。 证明：当证明：当i=1i=1时，由完全二叉树的定义，其左孩子是结点时，由完全二叉树的定义，其左孩子是结点2 2，右孩子是，右孩子是结点结点3 3，成立。，成立。当当i1i1时，分两种情况，此时只证最简单的一种情况，即设第时，分两种情况，此时只证最简单的一种情况，即设第j j层的第层的第一个结点的编号为一个结点的编号为i i，（由性质，（由性质2 2知，前知，前j-1j-1层共有层共有2 2j-1j-1-1-1个结点，所以个结点，所以第第j j层的第一个结点的编号为层的第一个结点的编号

20、为2 2j-1j-1，即，即i= i= 2 2j-1j-1），则其左孩子必为第），则其左孩子必为第j+1j+1层上的第一个结点，其编号为层上的第一个结点，其编号为2 2j j。( (因为第因为第j j层上有层上有2 2j j-1-1个结点个结点) )，而，而2 2j j=2(2=2(2j-1j-1)=2i)=2i，所以，编号为，所以，编号为i i的结点的左孩子的编号为的结点的左孩子的编号为2i2i。证明：根据性质证明：根据性质2 2，深度为，深度为k k的二叉树最多只有的二叉树最多只有2 2k k-1-1个结点，且完全二叉树个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结

21、点数的定义是与同深度的满二叉树前面编号相同，即它的总结点数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 n-lchildlchild) ; ) ; preorder ( preorder (btbt-rchildrchild) ; ) ; bcdefghji 二叉树的遍历二叉树的遍历1 1）中序遍历二叉树）中序遍历二叉树算法思想算法思想: : 若二叉树非空，则：若二叉树非空，则：

22、1 1）中序遍历左子树）中序遍历左子树2 2）访问根结点）访问根结点3 3）中序遍历右子树）中序遍历右子树算法描述算法描述:void inorder (bitree bt) /bt为根结点指针为根结点指针 if( bt) /根非空根非空 inorder (bt-lchild) ; inorder (bt-rchild) ; 362 2）后序遍历二叉树）后序遍历二叉树算法思想算法思想: : 若二叉树非空，则：若二叉树非空，则：1 1）后序遍历左子树）后序遍历左子树2 2）后序遍历右子树）后序遍历右子树3 3）访问根结点）访问根结点算法描述算法描述:void postorder (bitree b

23、t) /bt为根结点指针为根结点指针 if( bt) /根非空根非空 postorder (bt-lchild) ; postorder (bt-rchild) ; 37对遍历的分析：对遍历的分析：1. 从前面的三种遍历算法可以知道：如果将从前面的三种遍历算法可以知道：如果将print语句抹去，语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的遍历算法的访问路径是相同的，只是访问结点的时机不同访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径从虚线的出发点到终点的路径上，每个结点经过上，每个结点经过3次

24、次。afedcbg第第1次经过时访问先序遍历次经过时访问先序遍历第第2次经过时访问中序遍历次经过时访问中序遍历第第3次经过时访问后序遍历次经过时访问后序遍历2. 2. 二叉树遍历的时间效率和空间效率二叉树遍历的时间效率和空间效率时间效率时间效率: : /每个结点只访问一次每个结点只访问一次空间效率空间效率: : /栈占用的最大辅助空间栈占用的最大辅助空间（精确值：树深为（精确值：树深为k k的递归遍历需要的递归遍历需要k+1k+1个辅助单元！）个辅助单元！）38注：要实现遍历运算必须先把二叉树存入机内。注：要实现遍历运算必须先把二叉树存入机内。思路：思路：利用利用前序前序遍历来建树遍历来建树

25、（结点值陆续从键盘输入，用（结点值陆续从键盘输入，用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程序。程序。39知识回顾：知识回顾：（1 1）二叉树的存储：二叉树的存储： 顺序存储方式顺序存储方式： 完全二叉树完

26、全二叉树 满二叉树满二叉树 一般树补充成的完全二叉树或满二叉树一般树补充成的完全二叉树或满二叉树 链式存储方式链式存储方式：适用于各种树：适用于各种树（2 2）二叉树的遍历二叉树的遍历： 先序遍历、中序遍历、后序遍历、层序遍历先序遍历、中序遍历、后序遍历、层序遍历40a ab bj ji id dc cg gf fe eh h1 1、先序遍历的结果为：、先序遍历的结果为：2 2、中序遍历的结果为：、中序遍历的结果为：3 3、后序遍历的结果为：、后序遍历的结果为：a b d h e c f i g ja b d h e c f i g jd h b e a f i c j gd h b e a

27、f i c j gh d e b i f j g ch d e b i f j g c特点：先访问根，特点：先访问根， 再遍历左子树，再遍历左子树， 再遍历右子树再遍历右子树特点：先遍历左子树，特点：先遍历左子树， 再访问根，再访问根， 再遍历右子树再遍历右子树特点：特点： 先遍历左子树，先遍历左子树， 再遍历右子树再遍历右子树 最后访问根，最后访问根，41（3 3）二叉树的生成二叉树的生成按先序遍历方式生成按先序遍历方式生成注意注意：空节点的输入：空节点的输入42例：例：编写递归算法，计算二叉树中叶子结点的数目。编写递归算法，计算二叉树中叶子结点的数目。 思路：思路：输出叶子结点比较简单，用

28、任何一种遍历算法，凡输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。是左右指针均空者，则为叶子，将其统计并打印出来。 dlr(bitreebitree *root) /采用中序遍历的递归算法采用中序遍历的递归算法 if ( root!=null ) /非空二叉树条件，还可写成非空二叉树条件，还可写成if(root)if(root) if(!root-lchild&!root-rchild) /是叶子结点则统计并打印是叶子结点则统计并打印 sum+; printf(%dn,root-data); dlr(root-lchild); /递归遍历左

29、子树，直到叶子处；递归遍历左子树，直到叶子处； dlr(root-rchild); /递归遍历右子树，直到叶子处；递归遍历右子树，直到叶子处； return(0); 43习题讨论：习题讨论： 算法思路：算法思路：只查各结点后继链表指针，若左只查各结点后继链表指针，若左( (右右) )孩子的左孩子的左( (右右) )指针非空，则层次数加指针非空，则层次数加1 1；否则函数返回。；否则函数返回。左左子子树树右右子子树树根根hlhlhrhrheight=max(hl,hr)+1height=max(hl,hr)+1afedcbg44后序遍历求二叉树的高度递归算法：后序遍历求二叉树的高度递归算法：in

30、t posttreedepth(bitree bt)int posttreedepth(bitree bt) int hl,hr,max; int hl,hr,max; if(bt!=null) if(bt!=null) hl=posttreedepth hl=posttreedepth（bt-lchild); /bt-lchild); /求左子树的深度求左子树的深度 hr=posttreedepth(bt-rchild); /hr=posttreedepth(bt-rchild); /求右子树的深度求右子树的深度 max=hlhr?hl:hr; /max=hlhr?hl:hr; /* *得到

31、左、右子树深度较大者得到左、右子树深度较大者* */ / return (max+1); / return (max+1); /* *返回树的深度返回树的深度* */ / else return 0; else return 0; 45 算法思路：算法思路：既然要求从上到下，从左到右，则既然要求从上到下，从左到右，则利用队列利用队列存放各存放各子树结点的指针是个好办法，而不必拘泥于递归算法。子树结点的指针是个好办法，而不必拘泥于递归算法。技巧：技巧：当根结点出队后，令其左、右孩子结点入队，而左孩子当根结点出队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，出队时又令它的左右

32、孩子结点入队，由此便可产生按层次由此便可产生按层次输出的效果。输出的效果。adfcgehbvoid layout(bitree root)void layout(bitree root) enqueue(s,root); enqueue(s,root); while(!queueempty(s) while(!queueempty(s) dequeue(s,p); dequeue(s,p); printf( printf(“%c%c”,root-data);,root-data); enqueue(s,p-lchild); enqueue(s,p-lchild); enqueue(s,p-rc

33、hild); enqueue(s,p-rchild); 46算法思路：算法思路：若不用递归，则要实现二叉树遍历的若不用递归，则要实现二叉树遍历的“嵌套嵌套”规规则，必用堆栈。可直接用则，必用堆栈。可直接用whilewhile语句和语句和push/poppush/pop操作。操作。参见教材参见教材p130-131p130-131程序。程序。在中序遍历中，我们是通过顺着左子树的在中序遍历中，我们是通过顺着左子树的根直走到最左端，然后访问最左端元素，根直走到最左端，然后访问最左端元素，遍历右，再返回上一层，访问结点，遍历遍历右，再返回上一层，访问结点，遍历右，然后再访问上一层，这样又顺着左子右，然后

34、再访问上一层，这样又顺着左子树的根回到树的根回到a a。在递归调用中，返回上一层的操作是通过在递归调用中，返回上一层的操作是通过调用函数执行结束自然返回上一层的。如调用函数执行结束自然返回上一层的。如果不用递归，如何返回上一层。果不用递归，如何返回上一层。先从先从a a走到走到f f，在从，在从f f返回到返回到a a，最后走到的，最后走到的先访问，所以可以用栈。先访问，所以可以用栈。把根和左子树的根全部入栈把根和左子树的根全部入栈然后判断是否有右子树，如果有，则遍历然后判断是否有右子树，如果有，则遍历右子树，右子树，hiafedcbg4748证明：由一棵二叉树的先序序列和中序序列可唯一确定这

35、棵证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。二叉树。 例：例：已知一棵二叉树的已知一棵二叉树的中序序列中序序列和和后序序列后序序列分别是分别是bdceafhg 和和 decbhgfa，请画出这棵二叉树。，请画出这棵二叉树。分析：分析：由后序遍历特征，根结点必在后序序列尾部由后序遍历特征，根结点必在后序序列尾部（即（即a a）；由中序遍历特征，根结点必在其中间，而且其左部必全部是由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙左子树子孙（即（即bdcebdce），其右部必全部是右子树子孙，其右部必全部是右子树子孙（即（即fhgfhg）；继而，根据后序中的继而，根据

36、后序中的decbdecb子树可确定子树可确定b b为为a a的左孩子，根据的左孩子，根据hgfhgf子串可确定子串可确定f f为为a a的右孩子；以此类推。的右孩子；以此类推。49中序遍历：中序遍历：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 eghabbff506.4 树和森林1. 树和森林与二叉树的转换树和森林与二叉树的转换2. 树和森林的存储方式树和森林的存储方式3. 树和森林的遍历树和森林的遍历511234587961852 利用除根结点外每个结点只有唯一的双利用除根结点外每

37、个结点只有唯一的双亲的性质，以一组连续的空间存储树的结点，亲的性质，以一组连续的空间存储树的结点，同时在每个结点中附设一个指示域指示其双同时在每个结点中附设一个指示域指示其双亲结点在存储空间中的位置。亲结点在存储空间中的位置。6.4 树的存储结构树的存储结构一、一、双亲表示法双亲表示法#define max_tree_size 100#define max_tree_size 100结点结构：结点结构：typedef struct ptnode elem data; int parent; ptnode;data parentdata parenttypedef struct ptnode n

38、odesmax_tree_size; int r,n;536 .4 树的存储结构树的存储结构e ed da ab br rc cf fg gh hk k6h6g3f1e1d0c0b0a-1rk60 01 12 23 34 45 56 67 78 89 9r=0r=0n=10n=1054特点：特点：1 1）求结点的双亲操作可以在常量时间内实）求结点的双亲操作可以在常量时间内实现；现；2 2）求结点的孩子时需要遍历整个向量。）求结点的孩子时需要遍历整个向量。55二、孩子表示法二、孩子表示法孩子结点：孩子结点： typedef struct ctnode int child; struct ctno

39、de *next; *childptr;双亲结点双亲结点: typedef struct elem data; childptr firstchild; ctbox;56树结构：树结构： typedef structtypedef struct ctbox nodesmax_tree_size; ctbox nodesmax_tree_size; int n,r; int n,r; ctree; ctree; 57f fe eb bc ca ad dg gr=0r=0n=7n=70 01 12 23 34 45 56 6a ab bc cd de ef fg g1 12 23 34 45 56

40、 6-1-10 00 00 02 22 25 558三、树的二叉链表三、树的二叉链表 （孩子（孩子- -兄弟）存储表示法兄弟）存储表示法 typedef structtypedef struct csnode csnode elem data; elem data; struct csnode struct csnode * *firstchild,firstchild,* *nextsibling;nextsibling; csnode, csnode,* *cstree;cstree;59f fe eb bc ca ad dg ga ab bc ce ed df fg ga ab bc c

41、e ed df fg g601. 树和森林与二叉树的转换树和森林与二叉树的转换转换步骤：转换步骤：step1: step1: 将树中同一结点的兄弟相连将树中同一结点的兄弟相连; ;step2: step2: 保留结点的最左孩子连线，删除其它孩保留结点的最左孩子连线，删除其它孩子连线；子连线；step3: step3: 将同一孩子的连线绕左孩子旋转将同一孩子的连线绕左孩子旋转4545度角。度角。加线加线抹线抹线旋转旋转讨论讨论1 1：树如何转为二叉树？：树如何转为二叉树？61方法：方法：加加线线抹线抹线旋转旋转 abeidfhgc树转二叉树举例：树转二叉树举例：abeidfhgc兄弟相连兄弟相连

42、长兄为父长兄为父孩子靠左孩子靠左62讨论讨论2 2：二叉树怎样还原为树？：二叉树怎样还原为树？abeidfhgc要点：把所有右孩子变为兄弟！要点：把所有右孩子变为兄弟！ abeidfhgc63法一：法一： 各森林先各自转为二叉树；各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。依次连到前一个二叉树的右子树上。讨论讨论3 3：森林如何转为二叉树？：森林如何转为二叉树？法二：法二：森林直接变兄弟，再转为二叉树森林直接变兄弟，再转为二叉树（参见教材（参见教材p138p138图图6.176.17，两种方法都有转换示意图），两种方法都有转换示意图）即即f=tf=t1 1, t, t2 2, ,

43、 ,t,tm m b=root, lb, rb b=root, lb, rb64abcdefghjiabcdefghjibcdefghji森林转二叉树举例：森林转二叉树举例：（法二）（法二）兄弟相连兄弟相连 长兄为父长兄为父孩子靠左孩子靠左 头根为根头根为根 65讨论讨论4 4：二叉树如何还原为森林？：二叉树如何还原为森林？要点：要点：把最右边的子树变为森林，其余右子树变为兄弟把最右边的子树变为森林，其余右子树变为兄弟 abcdefghjiabcdefghjiefabcdghji即即b=root, lb, rb f=tb=root, lb, rb f=t1 1, t, t2 2, , ,t,t

44、m m 66树的遍历可有三条搜索路径：树的遍历可有三条搜索路径：先根序（次序）遍历先根序（次序）遍历 若树不空，则先访问根结点，然后依次先根遍若树不空，则先访问根结点，然后依次先根遍历各棵子树。历各棵子树。后根（次序）遍历后根（次序）遍历 若树不空，则先依次后根遍历各棵子树，然后若树不空，则先依次后根遍历各棵子树，然后访问根结点。访问根结点。按层次遍历按层次遍历 若树不空，则自上而下自左至右访问树中每个若树不空，则自上而下自左至右访问树中每个结点。结点。67c cf fe eb ba ad dg gh hi ij jk k先根遍历时顶点的访问先根遍历时顶点的访问次序：次序：a b e f c

45、d g h i j ka b e f c d g h i j k后根遍历时顶点的访问后根遍历时顶点的访问次序：次序：e f b c i j k h g d ae f b c i j k h g d a层序遍历时顶点的访问层序遍历时顶点的访问次序：次序：a b c d e f g h i j ka b c d e f g h i j k68 先序遍历先序遍历f若森林为空，返回；若森林为空，返回；f访问森林中第一棵树的根结点；访问森林中第一棵树的根结点；f先序遍历第一棵树中根结点的子树森林；先序遍历第一棵树中根结点的子树森林；f先序遍历除去第一棵树之后剩余的树构成的森林。先序遍历除去第一棵树之后剩

46、余的树构成的森林。 中序遍历中序遍历f若森林为空，返回；若森林为空，返回；f中序遍历森林中第一棵树的根结点的子树森林；中序遍历森林中第一棵树的根结点的子树森林；f访问第一棵树的根结点；访问第一棵树的根结点；f中序遍历除去第一棵树之后剩余的树构成的森林。中序遍历除去第一棵树之后剩余的树构成的森林。森林的遍历森林的遍历abcdefghji69abcdefghkiabcdefglj70路路 径径：路径长度路径长度：树的路径长度树的路径长度：带权路径长度带权路径长度：树的带权路径长度树的带权路径长度：霍霍 夫夫 曼曼 树树：6.5 huffman6.5 huffman树及其应用树及其应用一、最优二叉树

47、（一、最优二叉树（霍夫曼霍夫曼树）树）由一结点到另一结点间的分支所构成由一结点到另一结点间的分支所构成路径上的分支数目路径上的分支数目从树根到从树根到每一结点每一结点的路径长度之和。的路径长度之和。结点到根的路径长度与结点上权的乘积结点到根的路径长度与结点上权的乘积预备知识：若干术语预备知识：若干术语debacf g树中所有树中所有叶子结点叶子结点的带权路径长度之和的带权路径长度之和带权路径长度最小的树。带权路径长度最小的树。aeae的路径长度的路径长度树长度树长度2 2101071huffmanhuffman树简介：树简介：树的带权路径长度如何计算？树的带权路径长度如何计算？wplwpl =

48、 = 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 length72构造霍夫曼树的基本思想：构造霍夫曼树的基本思想：构造构造huffmanhuffman树的步骤（即树的步骤（即huffmanhuffman算法）：算法）：73操作要点：操作要点：对权值的合并、删除与替换对权值的合并、删除与替换在权值集合在权值集合7,5,2,47,5,2,4中，总是

49、合并中，总是合并当前值最小当前值最小的两个权的两个权构造构造huffmanhuffman树的步骤：树的步骤：注：方框表示外结点（叶子，字符对应的权值），注：方框表示外结点（叶子，字符对应的权值）， 圆框表示内结点（合并后的权值）。圆框表示内结点（合并后的权值）。6.2.2 6.2.2 赫夫曼编码赫夫曼编码74设有设有4 4个字符个字符d,i,a,nd,i,a,n，出现的频度分别为，出现的频度分别为7,5,2, 7,5,2, 4 4，怎样编码才能使它们组成的报文在网络中传得最快？，怎样编码才能使它们组成的报文在网络中传得最快？法法1 1：等长编码等长编码。例如用二进制编码来实现。例如用二进制编码

50、来实现。 取取 d=d=0000，i=i=0101，a=a=1010，n=n=1111法法2 2：不等长编码不等长编码，例如用前缀编码来实现。，例如用前缀编码来实现。 取取 d=d=0 0; i=; i=1010, a=, a=110110, n=, n=111111adin000111用用二二叉叉树树来来设设计计前前缀缀编编码码最快的编码是哪个？最快的编码是哪个？ 是非等长的前缀编码！是非等长的前缀编码！任一个字符的编任一个字符的编码都不是另一个码都不是另一个字符编码的前缀字符编码的前缀约定：约定：左分支表示左分支表示0 0右分支表示右分支表示1 1则从根结点到叶子结点的则从根结点到叶子结点

51、的路径上分支字符组成的字路径上分支字符组成的字符串作为该叶子的编码。符串作为该叶子的编码。75a ac cb bd de ek kf fg gh hi ij j76如何得到电文长度最短的二进制前缀编码？如何得到电文长度最短的二进制前缀编码？ 若按各个字符出现的概率不同而给予不等长编码，可望减若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。少总编码长度。d,i,a,nd,i,a,n，出现的频度分别为，出现的频度分别为7,5,2,47,5,2,4 假设每种字符在电文中出现的次数为假设每种字符在电文中出现的次数为w wi,i,，其编码长度为，其编码长度为l li i, ,电文中只有电

52、文中只有n n种字符，则电文总长度为种字符，则电文总长度为=niiliw1=niiliw1 由此可见，设计电文总长最短的二进制前缀编码即为以由此可见，设计电文总长最短的二进制前缀编码即为以n n种字符出现的频率作权，设计一颗赫夫曼树的问题，由此得到种字符出现的频率作权，设计一颗赫夫曼树的问题，由此得到的二进制前缀编码便称为赫夫曼编码。的二进制前缀编码便称为赫夫曼编码。 对应到二叉树上，若置对应到二叉树上，若置wiwi为叶子结点的权，为叶子结点的权， lili恰为从根恰为从根到叶子的路径长度。则：到叶子的路径长度。则： 恰为二叉树上带权路径长度。恰为二叉树上带权路径长度。77操作要点：操作要点：

53、按左按左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编码编码 挂钩挂

54、钩78例例2 2（严题集（严题集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的二进制编码方案的二进制编码方案又如何？又如何？霍

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

56、、替换），可得到哈夫曼树。79w4=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 717172

57、828212119194040w5=w5=28,28,32,32,4040 32326060w6=w6=40,6040,60 w7=w7=100100 100100b bc ca ad de eg gf fh h哈夫曼树哈夫曼树80对应的哈夫曼编码（左对应的哈夫曼编码（左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.

58、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 00000101001110010111011181另一种结果表示：另一种结果表示：82voidvoid huffmancoding(huffmantree &ht,huffmancode &hc, huffmancoding(huffmantree &ht,huff

59、mancode &hc,intint * *w,w,intint n) n) if(n=1) if(n=1) returnreturn; ;n n个权值构造一颗赫夫曼树需要的结点个数是：个权值构造一颗赫夫曼树需要的结点个数是：2n-12n-1这这 2n-1 2n-1 个结点的存储方式：个结点的存储方式：链式，链式，顺序顺序awawp pl lr r1 12 23 34 45 56 67 7m mawaw0 00 00 0bwbw0 00 00 0cwcw0 00 00 0dwdw0 00 00 0ewew0 00 00 0fwfw0 00 00 01 12 23 34 45 56 67 7m m0