《数据结构：第14章 树与二叉树》由会员分享，可在线阅读，更多相关《数据结构：第14章 树与二叉树（148页珍藏版）》请在金锄头文库上搜索。
1、n 线线性性表表、堆堆栈栈和和队队列列都都是是线线性性结结构构，它它们的共同特点：一对一；们的共同特点：一对一；n 计计算算机机对对弈弈中中的的一一个个格格局局可可能能有有多多个个后后继格局，用线性结构难以描述。继格局，用线性结构难以描述。n 树树是是一一种种非非线线性性结结构构，以以分分支支关关系系定定义义层次结构，适宜描述一对多的嵌套性数据。层次结构，适宜描述一对多的嵌套性数据。引入树引入树n 树和二叉树的基本概念树和二叉树的基本概念n 二叉树和树的存储结构二叉树和树的存储结构n 二叉树的抽象类二叉树的抽象类n 二叉树的遍历和树的遍历二叉树的遍历和树的遍历n 二叉排序树二叉排序树n 赫夫曼
2、树及其应用赫夫曼树及其应用 主要内容主要内容14.1 树和二叉树的基本概念树和二叉树的基本概念n 树的定义、术语及基本操作树的定义、术语及基本操作n 二叉树的定义及其性质二叉树的定义及其性质 树的定义树的定义n树是树是n（n=0）个结点的个结点的有限集合有限集合；n如果如果n=0，称为称为空树空树；n如果如果n0，即在一棵即在一棵非空树非空树中：中：(1)有有且且仅仅有有一一个个特特定定的的结结点点称称为为根根，它它只只有直接后继，但是有直接后继，但是没有直接前驱没有直接前驱； 树的定义树的定义（2）当）当n1时，其余结点可分为时，其余结点可分为m（m0）个互个互不相交的有限集合不相交的有限集
3、合T1，T2，.，Tm，其中其中每一个集合本身又是一棵树，并且称之为根的每一个集合本身又是一棵树，并且称之为根的子树子树。每棵子树的根结点有且仅有。每棵子树的根结点有且仅有一个一个直接前直接前驱，但可以有驱，但可以有0个或多个个或多个直接后继。直接后继。n可可见见，树树的的定定义义是是一一个个递递归归的的定定义义，即即树树的的定义中又用到树的概念，此即树的固有特性定义中又用到树的概念，此即树的固有特性。例：右面的图是例：右面的图是一棵树一棵树 T T = T = A A，B B，C C，D D，E E，F F，G G，H H，I I，J J A A是是根根，其余结点可以划分为，其余结点可以划分
4、为3 3个互不相交的集合：个互不相交的集合： T1= B,E,F T2= C,G T3= D,H,I,J T1= B,E,F T2= C,G T3= D,H,I,J 这些集合中的每一集合都本身又是一棵树，它们是这些集合中的每一集合都本身又是一棵树，它们是根根 A A 的的子树子树。 对于对于T1T1，B B是是根根，其余结点可以划分为两个互不相，其余结点可以划分为两个互不相交的集合：交的集合： T11= E T12= F T11T11= E T12= F T11，T12T12是是B B的的子树子树。J JI IA AC CB BD DH HG GF FE En从逻辑结构看：从逻辑结构看： 1）
5、树中只有）树中只有根根结点没有前趋；结点没有前趋； 2）除）除根根外，其余结点都外，其余结点都有且仅一个有且仅一个前趋；前趋； 3）树的结点，可以）树的结点，可以有零个有零个或或多个多个后继；后继； 4）除根外的其它结点，都存在唯一条从根到该结）除根外的其它结点，都存在唯一条从根到该结点的点的路径路径； 5）树是一种）树是一种分支结构分支结构（除了一个称为（除了一个称为根根的结点外）的结点外）每个元素都有且仅有一个直接前趋，每个元素都有且仅有一个直接前趋，有且仅有有且仅有零零个或多个直接后继。个或多个直接后继。J JI IA AC CB BD DH HG GF FE En树的应用树的应用 常用
6、的数据组织形式常用的数据组织形式计算机的文件系统。计算机的文件系统。 不论是不论是DOSDOS文件系统还是文件系统还是windowwindow文件系统，所有文件系统，所有的文件都是用树的形式进行组织。的文件都是用树的形式进行组织。文件夹文件夹1 1 文件夹文件夹n n 文件文件1 1 文件文件2 2文件夹文件夹21 21 文件夹文件夹22 22 文件文件21 21 文件文件2222C C 树的术语树的术语n树的结点树的结点：包含一个：包含一个数据元素的内容及若数据元素的内容及若干指向子树的分支。干指向子树的分支。n孩子结点孩子结点：结点的子树的：结点的子树的根称为该结点的孩子；如根称为该结点的
7、孩子；如B是是A的孩子。的孩子。n双亲结点双亲结点：B结点是结点是A结点的孩子，则结点的孩子，则A结点是结点是B结结点的双亲；如点的双亲；如B是是E的双亲。的双亲。n兄弟结点兄弟结点：同一双亲的孩子结点；如：同一双亲的孩子结点；如H、I、J互为兄互为兄弟。弟。n堂兄结点堂兄结点：同一层上结点；如：同一层上结点；如G与与E、F、H、I、J互为堂兄。互为堂兄。J JI IA AC CB BD DH HG GF FE E 树的术语树的术语J JI IA AC CB BD DH HG GF FE En祖先结点祖先结点：某一结点的：某一结点的祖先是从根到该结点所祖先是从根到该结点所经分支上的所有结点；如
8、经分支上的所有结点；如H的祖先为的祖先为A、D。n子孙结点子孙结点：以某结点为根的子树中的任一结点称为：以某结点为根的子树中的任一结点称为该结点的子孙；如该结点的子孙；如A的子孙为的子孙为B、C、D、E、F、G、H、I、J。n结点的度结点的度：结点子树的个数；如：结点子树的个数；如D的度为的度为3。n叶子结点叶子结点：也叫终端结点：也叫终端结点，是度为，是度为0的结点；如的结点；如E、F、G、H、I、J。n分支结点分支结点：度不：度不为为0的结点；如的结点；如A、B、C、D。 树的术语树的术语J JI IA AC CB BD DH HG GF FE En结点层次结点层次：根结点的层定义为根结点
9、的层定义为0，根的孩子为第根的孩子为第1层结点，依此类推。层结点，依此类推。n树的高度（深度）树的高度（深度）：树中结点的最大层次；如图所：树中结点的最大层次；如图所示树的高度为示树的高度为2。n树的度树的度：树中各结点的度的最大值；如图所示树的：树中各结点的度的最大值；如图所示树的度为度为3。任何一棵非空树是一个二元组任何一棵非空树是一个二元组Tree = （root，F） 其中：其中：root 称为根结点，称为根结点，F 称为子树森林。称为子树森林。森林：森林： 是是 m（m0）棵互不相交的树的棵互不相交的树的集合。集合。ArootBEFKLCGDHIJMF有序树：有序树：子树之间存在明确
10、的次序关系的树。子树之间存在明确的次序关系的树。无序树：无序树：不考虑子树的顺序。不考虑子树的顺序。 树的术语树的术语 树的基本操作树的基本操作n初始化初始化：即置：即置T为空树；为空树；n求求根根结结点点：即即求求树树T的的根根结结点点或或是是求求结结点点x所在树的根结点；所在树的根结点；n求双亲结点求双亲结点：求树：求树T中结点中结点x的双亲结点；的双亲结点；n求求孩孩子子结结点点：求求树树T中中结结点点x的的第第i个个孩孩子子结点。结点。 树的基本操作树的基本操作n求求右右兄兄弟弟：即即求求树树T中中结结点点x的的右右兄兄弟弟结结点；点；n建建立立一一棵棵树树：即即生生成成一一棵棵以以x
11、为为根根，以以森森林林F为子树的一棵树；为子树的一棵树；n插插入入子子树树：即即将将以以结结点点x为为根根的的子子树树T作作为树为树T中结点中结点y的第的第i棵子树。棵子树。 树的基本操作树的基本操作n删删除除子子树树：即即将将以以结结点点x为为根根的的第第i棵棵子子树树T从树从树T中删除；中删除；n遍遍历历：即即按按某某个个顺顺序序依依次次访访问问树树中中的的各各个结点，并使每个结点只被访问一次；个结点，并使每个结点只被访问一次；n清除清除：即将树：即将树T置为空树。置为空树。线性结构线性结构 VS 树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) )根结点根结点 ( (无
12、前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其他数据元素其他数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其他数据元素其他数据元素( (一个前驱、一个前驱、 多个后继多个后继) ) 二叉树的定义二叉树的定义n二叉树是一种普遍使用的树形结构；二叉树是一种普遍使用的树形结构；n二二叉叉树树(Binary Tree)或或为为空空树树，或或是是由由一一个个根根结结点点及及2棵棵不不相相交交的的左左子子树树和和右右子子树树构成，并且构成，并且左、右子树左、右子树本身也是本身也是二叉树二叉树；n二叉树的子树有左右之分，属于
13、二叉树的子树有左右之分，属于有序树有序树。ABCDEFGHK根结点根结点左子树左子树右子树右子树二叉树的例子二叉树的例子特点：特点：1）每个结点的度）每个结点的度2； 2）是有序树。）是有序树。二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树 二叉树的性质二叉树的性质1 ：若二叉树的层次从若二叉树的层次从0开始，则第开始，则第 i 层上至多有层上至多有2i 个结点个结点(i00)。用归纳法证明用归纳法证明： 1) i = 0 层时，只有一个根结点：层时，只有一个根结点：
14、2i = 20 = 1；2) 假设对所有的假设对所有的 j，0 j i，命题成立；命题成立；3) 二叉树上每个结点至多有两棵子树，则第二叉树上每个结点至多有两棵子树，则第 i 层的结点数是层的结点数是i-1层的层的2倍，即倍，即2i-1 2 = 2i 。 二叉树的性质二叉树的性质2 ：高度为高度为 k 的二叉树上至多含的二叉树上至多含 2k+11 个结点个结点（k-1）。）。证明：证明： 基于上一条性质，深度为基于上一条性质，深度为 k 的二叉的二叉树上的结点数至多为树上的结点数至多为 20+21+ +2k = 2k+1-1 。证明：证明：设，二叉树上结点总数设，二叉树上结点总数 n = n0
15、 + n1 + n2又，二叉树上进入结点的分支总数又，二叉树上进入结点的分支总数b： b = n1+2n2 ( (度为度为1 1的结点产生一条分支，度为的结点产生一条分支，度为2 2的结点产生的结点产生两条分支两条分支) ) b = n-1 ( (一个根结点的二叉树无分支，增加一个结点产生一一个根结点的二叉树无分支，增加一个结点产生一条分支条分支) )b b= n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1 。 二叉树的性质二叉树的性质3 ：对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n0 个叶子结点、个叶子结点、n2 个度为个度为 2 的结点，则必存在关系式：的
16、结点，则必存在关系式：n0 = n2+1。两种特殊的二叉树两种特殊的二叉树满二叉树满二叉树(Full Binary Tree) 如果高度为如果高度为k的二叉树，有的二叉树，有2k+1-1个结点，则个结点，则称为满二叉树；或者说在二叉树中每层的结称为满二叉树；或者说在二叉树中每层的结点数达到最大。点数达到最大。0123456789 10 11 12 13 14完全二叉树完全二叉树 (Complete Binary Tree) 1、树中所含的树中所含的 n 个结点和满二叉树中个结点和满二叉树中编号为编号为 1 至至 n 的结点的结点一一对应；一一对应；2、一棵二叉树，只有最下一层结点数未达到最大，
17、、一棵二叉树，只有最下一层结点数未达到最大，且最下层结点都集中在该层的最左端。且最下层结点都集中在该层的最左端。 两种特殊的二叉树两种特殊的二叉树abcdefghijabcde 叶子结点只可能在层次最大的两层叶子结点只可能在层次最大的两层上出现；上出现； 对任何一个结点，若其右子树的高对任何一个结点，若其右子树的高度为度为h，则其左子树的高度只能是则其左子树的高度只能是h或或h+1。完全二叉树的特点是：完全二叉树的特点是：证明：证明：设完全二叉树的高度为设完全二叉树的高度为 k ，结点数为结点数为n，则据第二条性质得则据第二条性质得2k-1 n 2k+1-1 2k n +1 2k+1 k n
18、，则该结点无左孩子则该结点无左孩子; 若若2i+1n ，编号为编号为 2i +1的结点为其的结点为其左孩子左孩子结点。结点。(3) 若若 2i+2n，则该结点无右孩子；则该结点无右孩子；若若2i+2n，编号为编号为2i+2 的结点为其的结点为其右孩子右孩子结点。结点。 若若 i=0，该结点是二叉树的根，该结点是二叉树的根， 无双亲无双亲; 若若 i0，编号为编号为 （i-1）/2 的结点为其的结点为其双亲双亲。若若2i+1n ，该结点无左孩子该结点无左孩子 (i=6,7); 若若2i+1n，编号为编号为 2i+1 的的 结点为其结点为其左孩子左孩子(i=3,4)。若若 2i+2n，该结点无右孩
19、子该结点无右孩子(i= 4,5,6); 若若2i+2n，编号为编号为2i+2 的结点为其的结点为其右孩子右孩子(i=2,3)。性质性质5举例举例0123456789小小 结结n 树的定义树的定义n 树的有关术语树的有关术语n 树的基本操作树的基本操作n 二叉树的定义二叉树的定义n 二叉树的性质二叉树的性质u 顺序存储结构：数组表示顺序存储结构：数组表示u 链式存储结构：二叉链表链式存储结构：二叉链表 三叉链表三叉链表14.2 二叉树的存储结构二叉树的存储结构对于完全二叉树，采用一组对于完全二叉树，采用一组连续的连续的内存单元，内存单元，按按编号编号顺序依次存储完全二叉树的结点。顺序依次存储完全
20、二叉树的结点。 0 1 2 3 4 5 6 0 1 2 3 4 5 6 A B C D E FA B C D E F A A F F E E D D C C B B0 01 12 23 34 45 5二叉树的顺序存储二叉树的顺序存储 对于一棵一般的二叉树，如果补齐构成完全二叉树所对于一棵一般的二叉树，如果补齐构成完全二叉树所缺少的那些结点，便可以对二叉树的结点进行编号。缺少的那些结点，便可以对二叉树的结点进行编号。 A A F F G G E E D D C C B B0 05 56 61 13 34 42 27 78 8 A A F F G G E E D D C C B B9 9二叉树的顺
21、序存储二叉树的顺序存储 将二叉树原有的结点按编号存储到内存单元将二叉树原有的结点按编号存储到内存单元“相相应应”的位置上。的位置上。0 05 56 61 13 34 42 27 78 8 A A F F G G E E D D C C B B9 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 A B A B C C D E D E 0 0 F F 0 00 0 G G二叉树的顺序存储二叉树的顺序存储 一般的二叉树会比完全一般的二叉树会比完全二叉树少很多结点，造成二叉树少很多结点，造成空空间浪费间浪费，例如单支树就是一，例如单支树就是一个极端情况。个极端情况。
22、顺序存储结构的缺点顺序存储结构的缺点二叉树的链式存储二叉树的链式存储1、二叉链表、二叉链表2、三叉链表三叉链表lchild data rchild结点结构结点结构:1. 二叉链表二叉链表ABDECFDataLChildRChildParentADEBCF root二叉链表图示二叉链表图示ABDECFstruct BintreeNode /结点结构结点结构 Type data; /结点的数据域结点的数据域 BintreeNode * Lchild; /左孩子指针左孩子指针 BintreeNode * Rchild; /右孩子指针右孩子指针 ;在建立其抽象类时，整个二叉树链表需要一个表在建立其抽象
23、类时，整个二叉树链表需要一个表头指针，它指向二叉树的根结点。头指针，它指向二叉树的根结点。二叉链表的结点二叉链表的结点lchild data rchild结点结构结点结构:ADEBCF root 2三叉链表三叉链表parent lchild data rchild结点结构结点结构:parent lchild data rchild结点结构结点结构:三叉链表的结点三叉链表的结点struct BintreeNode Type data; /结点的数据域结点的数据域 BintreeNode * Lchild; /左孩子指针左孩子指针 BintreeNode * Rchild; /右孩子指针右孩子指针
24、 BintreeNode * Parent ; /双亲结点指针双亲结点指针 ;小小 结结u 顺序存储结构：数组表示顺序存储结构：数组表示u 链式存储结构：二叉链表链式存储结构：二叉链表 三叉链表三叉链表14.3 树的存储结构与转换树的存储结构与转换n 树的存储结构树的存储结构n 树、森林与二叉树的转换树、森林与二叉树的转换 树的存储结构树的存储结构n 顺序存储结构：顺序存储结构：双亲表示法双亲表示法n 孩孩子子（双双亲亲）表表示示法法：（顺顺序序+ +链链式）式）n 孩子孩子- -兄弟表示法兄弟表示法：链式：链式 双亲表示法双亲表示法n 假假设设以以一一组组连连续续空空间间存存储储树树的的各各
25、结结点点，每每个个结点又设有两个域，结点类型如下：结点又设有两个域，结点类型如下：struct TreeNode Type data; /结点的数据域结点的数据域 TreeNode *Parent; /结点双亲指针结点双亲指针;data域域记记录录数数据据信信息息，Parent为为指指针针，它它指指向向其其双亲结点。双亲结点。 data parent结点结构结点结构:树的双亲表示法树的双亲表示法ABCDE F G0 A -11 B 02 C 03 D 04 E 1 5 F 26 G 27 H 2data parent数组下标数组下标H特点：特点：找双亲方便，找孩子难找双亲方便，找孩子难双亲结点
26、在数组中的位双亲结点在数组中的位置，置，-1-1表示无双亲表示无双亲 树的链式存储树的链式存储n多重链表多重链表n单链表单链表 通过保存树中每个结点的孩子结点的通过保存树中每个结点的孩子结点的位置，表示树中结点之间的结构关系。位置，表示树中结点之间的结构关系。n两种方式：两种方式：定长结点定长结点 和和 不定长结点不定长结点定长结点：定长结点：优点是结点结构一致，便于实优点是结点结构一致，便于实现树的操作。缺点是浪费一些内存空间。现树的操作。缺点是浪费一些内存空间。datachild1child2.childd不定长结点：不定长结点：优点是节省内存空间。缺点是不优点是节省内存空间。缺点是不定长
27、的结点会使一些操作实现变复杂。定长的结点会使一些操作实现变复杂。datadegreechild1child2.childd 多重链表（类似于二叉链表多重链表（类似于二叉链表） 将每个结点的孩子结点排列起来，构成一将每个结点的孩子结点排列起来，构成一个单链表，称为个单链表，称为孩子链表孩子链表； n个结点共有个结点共有n个孩子链表（叶子结点的孩个孩子链表（叶子结点的孩子链表为空表）；子链表为空表）； n个结点的孩子链表头指针又组成一个个结点的孩子链表头指针又组成一个顺顺序表。序表。单链表表示法单链表表示法 线性表线性表 + 单链表单链表此时，单链表中各结点由两个域构成：此时，单链表中各结点由两个
28、域构成：struct TreeNode / 结点定义结点定义 Type data; TreeNode *next ;TreeNode *vertexn; /顺序表是一个指顺序表是一个指针数组，数组元素是指向孩子链表的头指针，针数组，数组元素是指向孩子链表的头指针，n个结点个结点n个指针。个指针。孩子链表表示法孩子链表表示法ABCDEFG data firstchild0 A1 B2 C3 D4 F5 E6 G64 5 1 2 3同一结点的同一结点的孩子构成链表孩子构成链表孩子链表存储表示孩子链表存储表示 孩子表示法便于实现涉及孩子的操孩子表示法便于实现涉及孩子的操作，却不适用于涉及双亲的操作。
29、作，却不适用于涉及双亲的操作。 将双亲指针加入可以同时方便有关将双亲指针加入可以同时方便有关孩子和双亲的操作。孩子和双亲的操作。 孩子双亲表示法孩子双亲表示法孩子孩子- -兄弟表示法兄弟表示法n孩孩子子-兄兄弟弟表表示示法法又又称称二二叉叉树树表表示示法法，或或二叉链表表示法二叉链表表示法；n链链表表中中结结点点的的两两个个指指针针域域分分别别指指向向该该结结点点的的第第一一个个孩孩子子结结点点和和下下一一个个兄兄弟弟结结点点，分分别命名为别命名为FirstChild和和NextSibling域。域。结点结构结点结构: firstchild data nextsibling 孩子孩子- -兄弟
30、表示法兄弟表示法struct TreeNode /结点结构结点结构 Type data; TreeNode * FirstChild; /第一个孩子指针第一个孩子指针 TreeNode * NextSibling; /下一个兄弟指针下一个兄弟指针; /sibling:兄兄弟弟, 姐妹姐妹如下图所示：如下图所示：ABCDEFG AB C E D F Groot孩子兄弟表示法图示孩子兄弟表示法图示C C的第一个的第一个孩子结点孩子结点E EE E的紧邻的的紧邻的右兄弟结点右兄弟结点 便于实现各种树的操作。便于实现各种树的操作。 易于查找结点的孩子结点易于查找结点的孩子结点。例如要访问。例如要访问结
31、点结点x的第的第i个孩子，则只要先从个孩子，则只要先从FirstChild域域找到第一个孩子结点，然后沿着孩子结点的找到第一个孩子结点，然后沿着孩子结点的NextSibling 域连续走域连续走i-1步，便可找到步，便可找到x的第的第i个孩子结点。个孩子结点。 如果为每个结点增设一个如果为每个结点增设一个Parent域，则同域，则同样能方便地实现样能方便地实现求双亲结点求双亲结点的操作。的操作。 孩子孩子- -兄弟表示法优点兄弟表示法优点 树、森林与二叉树的转换树、森林与二叉树的转换n树与二叉树之间的转换树与二叉树之间的转换n森林与二叉树之间的转换森林与二叉树之间的转换ABCDEFG AB C
32、 E D F Groot AB C E D F G 孩子兄弟表示法图示孩子兄弟表示法图示树和森林的表示方法树和森林的表示方法 树树的的孩孩子子兄兄弟弟链链表表结结构构与与二二叉叉树树的的二二叉叉链链表表结结构构，都都以以二二叉叉链链表表作作为为存存储储结结构构，它它们们的的物物理结构完全相同；理结构完全相同； 在树和二叉树之间必然存在在树和二叉树之间必然存在一一对应一一对应关系；关系； 如如果果把把森森林林中中第第二二棵棵树树的的根根结结点点看看成成是是第第一一棵棵树树根根结结点点的的兄兄弟弟，同同样样可可导导出出森森林林与与二二叉叉树树的对应关系。的对应关系。 I IA AC CB BD D
33、H HG GF FE E树根结点X的第一个孩子结点X紧邻的右兄弟二叉树根结点X的左孩子结点X左孩子的右孩子树与二叉树的转换树与二叉树的转换 F FI IA AB BD DH HG GC CE En森林与二叉树的转换森林与二叉树的转换 森林：树的集合森林：树的集合 将将森林中森林中树的根看成兄弟树的根看成兄弟，用树与二叉，用树与二叉树的转换方法，可进行森林与二叉树转换。树的转换方法，可进行森林与二叉树转换。ABCDEFGHIJABCDEFGHIJABCDEFGHIJ小小 结结n树的存储结构树的存储结构n 树、森林与二叉树的转换树、森林与二叉树的转换n 顺序存储结构：顺序存储结构：双亲表示法双亲表
34、示法n 孩子（双亲）表示法孩子（双亲）表示法：（顺序：（顺序+ +链式）链式）n 孩子孩子- -兄弟表示法兄弟表示法：链式：链式n树与二叉树之间的转换树与二叉树之间的转换n森林与二叉树之间的转换森林与二叉树之间的转换14.4 二叉树的抽象二叉树的抽象类类n二叉树结点类二叉树结点类n二叉树的抽象类二叉树的抽象类u 结点类的定义：结点类的定义： /类的提前引用声明：类的提前引用声明：二叉树类二叉树类template class BinaryTree; /类的提前引用声明：类的提前引用声明：二叉排序树类二叉排序树类template class BST; template class BinTreeN
35、ode /将将BinaryTree类类声明为声明为BinaryTreeNode类的友元类类的友元类 friend class BinaryTree; /将将BST类声明为类声明为BinaryTreeNode类的友元类类的友元类 friend class BST;public: BinTreeNode( ); /构造函数构造函数 BinTreeNode(T & value); /传结点数据构造函数传结点数据构造函数 BinTreeNode(T & value, BinTreeNode*left, BinTreeNode*right); /分支结点构造函分支结点构造函数数 void release
36、( ); /删除当前结点的左右子删除当前结点的左右子树树 T &GetData( )const return data; BinaryTreeNode GetLeft( )const return Lchild; BinaryTreeNode GetRight( )const return Rchild; const的含义：该成的含义：该成员函数的算法不修改员函数的算法不修改该类的成员变量的值该类的成员变量的值 void SetData(T & value) data=value; /修改结点数据值修改结点数据值 void SetLeft(BinTreeNode *L); /修改结点左孩子指针
37、修改结点左孩子指针 void SetRight(BinTreeNode *R); /修改结点右孩子指针修改结点右孩子指针private: T data; /数据域数据域 BinTreeNode *Lchild; /左孩子指针左孩子指针 BinTreeNode *Rchild; /右孩子指针右孩子指针 ；u 无参构造函数无参构造函数：构造无值结点，无左右子树：构造无值结点，无左右子树templateBinTreeNode:BinTreeNode( ):Lchild(NULL), Rchild(NULL) /参数初始参数初始化表化表 u 传结点数据的构造函数传结点数据的构造函数：构造有值结点，无：
38、构造有值结点，无左右子树左右子树templateBinTreeNode:BinTreeNode(T & value) data=value; Lchild=Rchild=NULL; u 带子树的结点构造函数带子树的结点构造函数：构造有值、有左右：构造有值、有左右子树的结点子树的结点templateBinTreeNode:BinTreeNode(T & value, BinTreeNode*left, BinTreeNode*right) data=value; Lchild=left; Rchild=right; u 释放子树空间释放子树空间：释放以某结点为根的子树中所有结释放以某结点为根的子
39、树中所有结点的存储空间，但点的存储空间，但不释放根结点不释放根结点所占的存储空间。所占的存储空间。templatevoid BinTreeNode:release( ) if(Lchild!=NULL) Lchild-release( ); /递归调用释放左子树递归调用释放左子树 delete Lchild; Lchild=NULL: if(Rchild!=NULL) Rchild-release( ); /递归调用释放右子树递归调用释放右子树 delete Rchild; Rchild=NULL: u 设置新的左子树：设置新的左子树：在给一个左子树或右子树在给一个左子树或右子树重新赋值之前，
40、必须重新赋值之前，必须先释放掉先释放掉该指针原来所指该指针原来所指向的子树的所有结点。向的子树的所有结点。templatevoid BinTreeNode:SetLeft(BinTreeNode *L) Lchild-release( ); /释放原来的左子树释放原来的左子树 delete Lchild; /释放左子树的释放左子树的根根结点结点 Lchild=L; /修改左指针修改左指针u设置新的右子树设置新的右子树templatevoid BinTreeNode:SetRight(BinTreeNode *R) Rchild-release( ); /释放原来的右子树释放原来的右子树 del
41、ete Rchild; /释放右子树的释放右子树的根根结点结点 Rchild=R; /修改右指针修改右指针 二叉树的抽象二叉树的抽象类类template class BinaryTree public: BinaryTree( ); /构造一棵空的二叉树构造一棵空的二叉树 BinaryTree(const BinaryTree&source);/复制二叉树复制二叉树 /以以value为根，为根，left和和right为左右子树构造一棵二叉树为左右子树构造一棵二叉树 BinaryTree(T value, BinTreeNode*left, BinTreeNode*right); /析构函数，释
42、放二叉树所有结点所占的存储空间析构函数，释放二叉树所有结点所占的存储空间 BinaryTree( ); void DeleteAllValues( ); /清除操作，使树变为空树清除操作，使树变为空树 /判二叉树空否，若二叉树为空，返回判二叉树空否，若二叉树为空，返回1，否则返回，否则返回0 int IsEmpty( ); constconst类型的形参类型的形参: :只只用于赋给别的变量用于赋给别的变量, ,它本身不能被修改它本身不能被修改/在在以以t为根为根的二叉树中查找，找到值等于的二叉树中查找，找到值等于value的结点的结点 时，返回该结点地址，否则返回空指针时，返回该结点地址，否则
43、返回空指针 virtualBinaryTreeNode*Find(BinaryTreeNode*t,T &value)=0;/在在当前当前二叉树中查找数据域值等于二叉树中查找数据域值等于value的结点的结点 virtual BinaryTreeNode*Find(T &value)=0；/返回返回当前当前二叉树中删除的一个元素二叉树中删除的一个元素virtual int Delete(const T &value)=0;BinaryTreeNode*LeftChild(T &value); /返回左孩子返回左孩子BinaryTreeNode*RightChild(T &value); /返回
44、右孩子返回右孩子void Traver(BinaryTreeNode*current); /current为根遍历二叉树为根遍历二叉树void Traver( ); /遍历以遍历以root为根的二叉树为根的二叉树BinaryTreeNode*GetRoot( ) constreturn root; /取取根根/输入运算符重载输入运算符重载frind istream &operator(istream &in, BinaryTree &Tree); /输出运算符重载输出运算符重载frind ostream &operator(istream &out, BinaryTree &Tree); pr
45、otected: BinaryTreeNode *root; ;u 构造空树的函数构造空树的函数templateBinaryTree:BinaryTree( ) root=NULL;u 拷贝构造函数拷贝构造函数templateBinaryTree:BinaryTree(const BinTree &source) root = source.root-copy( );u 构造函数：构造函数：新构造一个新构造一个根结点根结点，将已知两，将已知两棵树分别作为左、右子树。棵树分别作为左、右子树。调用结点类的带调用结点类的带参构造函数参构造函数templateBinaryTree:BinaryTree
46、(T value, BinaryTreeNode*left, BinTreeNode*right) root=new BinaryTreeNode(value, left, right); u析构函数：析构函数：使用结点类中的使用结点类中的release函数，函数， release函数只删除两个子树中的结点，因此函数只删除两个子树中的结点，因此最后需要删除根结点。最后需要删除根结点。templateBinaryTree : BinaryTree( ) root-release( ); delete root; root=NULL;u 删除整棵树中的所有结点删除整棵树中的所有结点：删除树中所有的
47、删除树中所有的结点，最后将根指针置空。结点，最后将根指针置空。templatevoid BinaryTree:DeletAllValues( ) root-release( ); delete root; root=NULL; u 判定二叉树是否为空判定二叉树是否为空：检查检查根指针根指针是否为空。是否为空。templateint BinaryTree:IsEmpty( ) return root=NULL; /root=NULL逻辑表达式逻辑表达式u 返回左孩子地址返回左孩子地址templateBinaryTreeNode*BinaryTree:LeftChild(T &value) Bin
48、aryTreeNode *current=Find(value); if(current!=NULL) return current-GetLeft( ); else return NULL;u 返回右孩子地址返回右孩子地址template BinaryTreeNode*BinaryTree:RightChild(T &value) BinaryTreeNode*current=Find(value); if(current!=NULL) return current-GetRight( ); else return NULL;u 输入流运算符重载输入流运算符重载：输入并建立一棵输入并建立一棵
49、二叉排序树二叉排序树，用重载运算符来实现。用重载运算符来实现。template istream & operator(istream &in, BinaryTree &Tree) T item, Ref; /定义定义2个数据元素类型的变量个数据元素类型的变量 cout“Construct binary tree:n”; coutRef; /输入参考结点值输入参考结点值 cout“Input data(end with”Refitem; while(item!=Ref) /二叉排序树中不存在值相等的结点二叉排序树中不存在值相等的结点 Tree.Insert(item); initem; retu
50、rn in;u 输出流运算符重载输出流运算符重载：输出一棵二叉树，需要用输出一棵二叉树，需要用到二叉树的遍历函数到二叉树的遍历函数Traver，Traver函数的算法是：函数的算法是：在在遍历结点的同时输出遍历结点的同时输出所遍历到的结点值。所遍历到的结点值。template ostream & operator(ostream &out, BinaryTree &Tree) cout“Traversal of binary tree:n”; Tree.Traver(Tree.root); /Traver是二叉树的遍历函数是二叉树的遍历函数 return out;小结小结n二叉树的结点类二叉树
51、的结点类n二叉树的抽象类二叉树的抽象类14.5 二叉树二叉树的遍历的遍历1、遍历的概念、遍历的概念2、二叉树的遍历、二叉树的遍历3、二叉树遍历的应用、二叉树遍历的应用1、遍历的基本概念n 遍历：遍历：按某种按某种搜索路径搜索路径访问二叉树中的访问二叉树中的每个每个结点，而且每个结点仅被结点，而且每个结点仅被访问访问一次。一次。n 访问访问：含义很广，可以是对结点的各种含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据等。处理，如修改结点数据、输出结点数据等。n 遍历是各种数据结构遍历是各种数据结构最基本的操作最基本的操作，许，许多其它的操作可以在遍历基础上实现。多其它的操作可以在遍
52、历基础上实现。n 遍历对遍历对线性结构线性结构来说很容易解决，但是来说很容易解决，但是二叉树二叉树每个结点都可能有两棵子树，因而每个结点都可能有两棵子树，因而需要寻找一种规律，使得二叉树上的结点需要寻找一种规律，使得二叉树上的结点能排列成线性。能排列成线性。2、二叉树的遍历、二叉树的遍历二二叉叉树树由由三三部部分分组组成成：根根结结点点、左左子子树树、右子树；右子树；若若能能依依次次遍遍历历这这三三部部分分，就就遍遍历历完完了了整整个个二叉树。二叉树。 L：遍历左子树遍历左子树 D：访问根结点访问根结点 R：遍历右子树遍历右子树 先左后右：先左后右：DLR、LDR、LRD 先先右右后后左左：
53、DRL、RDL、RLDq 先先(根根)序遍历序遍历 q 中中(根根)序遍历序遍历q 后后(根根)序遍历序遍历先左后右先左后右的遍历算法的遍历算法先先(根根)序遍历序遍历先序遍历先序遍历DLR递归描述递归描述基本项：若二叉树为空，结束基本项：若二叉树为空，结束递归项：递归项：（1）访问根结点；）访问根结点；（2）先序遍历左子树；）先序遍历左子树；（3）先序遍历右子树。）先序遍历右子树。ABCFDGE先序遍历序列（先序遍历序列（DLR）：）：A B D E G C Fn先序遍历算法如下：先序遍历算法如下：template void BinaryTree :PreOrder( ) /先序遍历先序遍历
54、当前当前二叉树二叉树 PreOrder(root);/先序遍历先序遍历以以current为根为根的子树，的子树，递归函数递归函数templatevoid BinaryTree:PreOrder(BinTreeNode *current)/current=NULL，即到达叶子结点是递归终止条件即到达叶子结点是递归终止条件 if(current!=NULL) coutdata; /访问根结点访问根结点,用输出语句暂代用输出语句暂代 PreOrder(current-leftChild); /先序遍历左子树先序遍历左子树 PreOrder(current-rightChild); /先序遍历右子树先
55、序遍历右子树 中中(根根)序遍历序遍历中序遍历递归描述中序遍历递归描述基本项：若二叉树为空，结束基本项：若二叉树为空，结束递归项：递归项：（1）中序遍历左子树；）中序遍历左子树；（2）访问根结点；）访问根结点；（3）中序遍历右子树。）中序遍历右子树。中序遍历序列（中序遍历序列（LDR）：）：D B G E A F CABCFDGEn中序遍历算法如下：中序遍历算法如下：templatevoid BinaryTree :InOrder( ) /中序遍历中序遍历当前当前二叉树二叉树 InOrder(root);/中序遍历中序遍历以以current为根为根的子树，的子树，递归函数递归函数templat
56、e void BinaryTree:InOrder(BinTreeNode *current) if(current!=NULL) /current=NULL为递归终止条件为递归终止条件 InOrder(current-LChild); /中序遍历左子树中序遍历左子树 coutdata; /访问根结点，用输出语句暂访问根结点，用输出语句暂代代 InOrder(current-RChild); /中序遍历右子树中序遍历右子树 后后(根根)序遍历序遍历后序遍历递归描述后序遍历递归描述基本项：若二叉树为空，结束基本项：若二叉树为空，结束递归项：递归项：（1）后序遍历左子树；）后序遍历左子树；（2）后
57、序遍历右子树；）后序遍历右子树；（3）访问根结点。）访问根结点。后序遍历序列（后序遍历序列（LRD）：）：D G E B F C AABCFDGEn后序遍历算法如下后序遍历算法如下：template void BinaryTree :PostOrder( )/后序遍历后序遍历当前当前二叉树二叉树 PostOrder(root);/后序遍历后序遍历以以current为根为根的子树，的子树，递归函数递归函数templatevoid BinaryTree:PostOrder(BinTreeNode *current) if(current!=NULL)/current=NULL是递归终止条件是递归终
58、止条件 PostOrder(current-leftChild); /后序遍历左子树后序遍历左子树 PostOrder(current-rightChild);/后序遍历右子树后序遍历右子树 coutdata; /访问根结点访问根结点, 用输出语句用输出语句代代 3、二叉树遍历的应用二叉树遍历的应用n计算二叉树结点个数计算二叉树结点个数n计算二叉树的高度计算二叉树的高度n判断两棵二叉树是否相等或等价判断两棵二叉树是否相等或等价 1）计算二叉树结点个数）计算二叉树结点个数n利用二叉树的后序遍历规则，先遍历左子树和右利用二叉树的后序遍历规则，先遍历左子树和右子树，分别计算出子树，分别计算出左子树左
59、子树和和右子树右子树中的结点个数，中的结点个数，然后把访问然后把访问根结点根结点加进去，就可以得到整个二叉加进去，就可以得到整个二叉树的结点个数。树的结点个数。templateint BinaryTree:Size(const BinTreeNode *t)const /计算计算以以t为根为根的二叉树的结点个数的二叉树的结点个数 if(t=NULL) return 0; /递归结束条件为空树，结点个数递归结束条件为空树，结点个数为为0 else return 1+Size(t-LChild)+Size(t-RChild); 2）计算二叉树的高度）计算二叉树的高度n如果二叉树为如果二叉树为空树空
60、树，高度为，高度为-1；否则按后序遍历规则，先否则按后序遍历规则，先递归计算根结点的递归计算根结点的左子树和右子树的高度，左子树和右子树的高度，再求出两者再求出两者中中较大者，并较大者，并加加1（要包括根结点，高度加（要包括根结点，高度加1），就可以），就可以得到整个二叉树的高度。得到整个二叉树的高度。templateint BinaryTree:Depth(const BinTreeNode *t)const /计算计算以以t为根的二叉树的高度为根的二叉树的高度 if (t=NULL) return -1; /递归结束条件为空树，空树高度为递归结束条件为空树，空树高度为-1 else ret
61、urn 1+Max(Depth(t-LChild)，Depth(t-RChild); 其中其中Max函数是求两者中的较大者：函数是求两者中的较大者：int Max(int x,int y) return(xy ? x:y);3）判断两棵二叉树是否相等或等价）判断两棵二叉树是否相等或等价template /= =运算符重载运算符重载int operator=(const BinTreeNode &a, const BinTreeNode &b) /判断两棵二叉树的等价性判断两棵二叉树的等价性 return equal(a.root, b.root); /如果如果a和和b的子树不等同，则函数返回的
62、子树不等同，则函数返回0，否则函数返回，否则函数返回1templateint equal(BinTreeNode&a, BinTreeNode&b)/递归函数递归函数 if(a=NULL & b=NULL) return 1; /两者两者都为都为NULL/a与与b根结点的数据相同，且它们的左、右子树也相同根结点的数据相同，且它们的左、右子树也相同 if(a!=NULL & b!=NULL & a-data=b-data & equal(a-Lchild, b-LChild) & equal(a-Rchild, b-RChild) ) return 1; return 0; 仅知二叉树的先序序列
63、“abcdefg” 不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？ 二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列先序序列中序序列中序序列例例: :试分别找出满足以下条件的所有二试分别找出满足以下条件的所有二叉树。叉树。（1 1）二叉树的前序序列与中序序列相同）二叉树的前序序列与中序序列相同 空空树或缺左子树的单支树树或缺左子树的单支树（2
64、2）二叉树的中序序列与后序序列相同）二叉树的中序序列与后序序列相同 空空树或缺树或缺右子右子树的单支树树的单支树（3 3）二叉树的前序序列与后序序列相同）二叉树的前序序列与后序序列相同 空空树或树或只有根结点的二叉树只有根结点的二叉树 已知一棵二叉树的前序序列与中已知一棵二叉树的前序序列与中序序列分别为：序序列分别为： ABCDEFGHI BCAEDGHFI试构造出这棵二叉树。试构造出这棵二叉树。前序前序：ABCDEFGHI 中序：中序：BCAEDGHFI小结小结n 二叉树的遍历二叉树的遍历n二叉树的遍历二叉树的遍历n二叉树遍历的应用二叉树遍历的应用n深度优先遍历深度优先遍历u先根次序遍历先根
65、次序遍历u后根次序遍历后根次序遍历n广度优先遍历广度优先遍历14.6 树的遍历树的遍历u 深度优先遍深度优先遍历历n第一步：访问树的根结点；第一步：访问树的根结点；n第二步：第二步：“先根次序先根次序”遍历根的第一棵子树；遍历根的第一棵子树；n第第三三步步：“先先根根次次序序”遍遍历历根根的的第第二二棵棵子子树树、第三第三棵子树，棵子树， , 直至遍历完整直至遍历完整棵树。棵树。 先根次序遍历先根次序遍历 后根次序后根次序遍历遍历n第第一一步步： “后后根根次次序序”遍遍历历根根的的第第一一棵棵子树；子树；n第第二二步步：“后后根根次次序序”遍遍历历根根的的第第二二棵棵子子树树、第第三三棵棵子
66、子树树，, 直直至至遍遍历历根根的的所所有子树；有子树；n第三步：访问根结点第三步：访问根结点。u 广度优先广度优先遍历遍历n按层次进行访问遍历：按层次进行访问遍历：第一步，访问层次为第一步，访问层次为0 的根结点；的根结点；第第二二步步，自自左左向向右右顺顺序序访访问问层层次次为为1的的各个结点；各个结点；第第三三步步，自自左左向向右右顺顺序序访访问问层层次次为为2的的各个结点；各个结点；n直至所有的结点都访问完。直至所有的结点都访问完。n树的遍历实例树的遍历实例ABCDEFGHIJKLMNO先序遍历：先序遍历：后序遍历：后序遍历：层次遍历：层次遍历：ABE F I GCDHJ K LNOM
67、E I FGB CJK NOLM HDAABCDEFGHI J K LMNO小结小结n 树的遍历树的遍历n深度优先遍历深度优先遍历u先根次序遍历先根次序遍历u后根次序遍历后根次序遍历n广度优先遍历广度优先遍历14.7 二叉排序二叉排序树树n二叉排序树的定义二叉排序树的定义n二叉排序树的查找过程二叉排序树的查找过程n二叉排序树的插入、删除操作二叉排序树的插入、删除操作1、定义、定义（1）若它的左子树不空，则左子树上）若它的左子树不空，则左子树上 所有所有结点的值结点的值均小于均小于根结点的值；根结点的值； 二叉排序树二叉排序树或者是一棵空树；或者或者是一棵空树；或者是具有如下特性的二叉树：是具有
68、如下特性的二叉树：（3）它的左、右子树）它的左、右子树也都也都分别分别是二叉是二叉 排序树排序树。（2）若它的右子树不空，则右子树上）若它的右子树不空，则右子树上 所有所有结点的值结点的值均大于均大于根结点的值；根结点的值；503080209010854035252388例如例如:是二叉排序树。是二叉排序树。66不不u 二叉排序树类的定义二叉排序树类的定义：它是它是BinaryTree类的派生类的派生类，类，BinTreeNode的友元类。的友元类。templateclass BST: public BinaryTreepublic: / 其他成员函数的声明与其他成员函数的声明与定义定义 /在
69、在以以t为根为根的二叉树中找到值为的二叉树中找到值为value的结的结点时，返回其地址点时，返回其地址 BinTreeNode *Find(BinTreeNode *t,T&value); BinTreeNode *Find(T&value); /在在当前二当前二叉树叉树中查找中查找 /在在以以t为根为根的二叉树找到值为的二叉树找到值为value的结点时，的结点时，则不插入，返回则不插入，返回0；否则将其插入到二叉树中，；否则将其插入到二叉树中，返回返回1 int Insert(BinTreeNode *t,T&value); int Insert(T&value);/在在当前二叉树当前二叉树
70、中插入值中插入值为为value的新结点的新结点 /在在以以t为根为根的二叉树中找不到值为的二叉树中找不到值为value的结点的结点时，返回时，返回0；否则将其从二叉树中删除，返回；否则将其从二叉树中删除，返回1 int Delete(BinTreeNode *t,T&value); int Delete(T&value); ；/在在当前二叉树当前二叉树中删中删除值为除值为value的结点的结点2二叉排序树的查找过程二叉排序树的查找过程1）若给定值）若给定值等于等于根结点的关键字，则查找成功；根结点的关键字，则查找成功；2）若给定值）若给定值小于小于根结点的关键字，则继续在左子根结点的关键字，则
71、继续在左子树上进行递归查找；树上进行递归查找；3）若给定值）若给定值大于大于根结点的关键字，则继续在右子根结点的关键字，则继续在右子树上进行递归查找。树上进行递归查找。从根结点开始，若二叉排序树从根结点开始，若二叉排序树为空为空，则查找，则查找不成功；否则，不成功；否则，关键字关键字：二叉排序树建立时所依据的结点：二叉排序树建立时所依据的结点值，能值，能唯一唯一地表示该结点，且所有的关键地表示该结点，且所有的关键字字互不相同互不相同。50308020908540358832例如例如:二叉排序树二叉排序树查找关键字查找关键字= 50 ,505035 ,503040355090 ,50809095
72、 ,从上述查找过程可见，从上述查找过程可见，在查找过程中，生成了一条查找路径查找路径： 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点逐层向下直至关键字等于给定值的结点;或者 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。逐层向下直至指针指向空树为止。 查找成功查找成功 查找不成功查找不成功 二叉排序树的查找算法二叉排序树的查找算法n递归算法递归算法n迭代算法迭代算法u 递归算法：递归算法：在在以以t为根为根的树中查找值为的树中查找值为value的结点的结点templateBinTreeNode
73、*BST:Find(BinTreeNode *t, T &value) /空树或查找成功，返回空树或查找成功，返回 if (t=NULL | t-data=value) return t; else if(value data) /否则，继续查找左子树否则，继续查找左子树 return (Find(t-Lchild, value); /否则，继续查找右子树否则，继续查找右子树 else return (Find(t-Rchild, value); u 迭代算法：迭代算法：在在以以t为根为根的树中查找值为的树中查找值为value的结点的结点templateBinTreeNode*BST:Find
74、(BinTreeNode *t, T &value) if(t!=NULL) /树非空树非空 BinTreeNode *s=t; /从根开始查找从根开始查找 while(s!=NULL) /等于等于NULL表示表示查找失败查找失败 if (value = s-data) return s; /查找成功查找成功 if(value s-data) s=s-GetRight( ); / 否则否则,继续查找继续查找 右子树右子树 else s=s-GetLeft( ); / 否则否则,继续查找继续查找 左子树左子树 return NULL； / 树空树空, 返回返回u 定义了上述定义了上述Find函数
75、，即可定义函数，即可定义当前当前二叉二叉排序树的查找函数：排序树的查找函数：templateBinTreeNode*BST:Find(T&value) if(root=NULL) /如果当前树为空树，直接返回如果当前树为空树，直接返回 /NULL return NULL; else return Find(root, value);“插入插入”操作在操作在查找查找不成功不成功时才进行时才进行 3 3、二叉排序树的插入、二叉排序树的插入 n二叉排序树是一种二叉排序树是一种动态树表动态树表；n特点特点：树的结构通常：树的结构通常不是一次生成不是一次生成的，而的，而是在查找过程中，当树中是在查找过程
76、中，当树中不存在不存在关键码等关键码等于给定值的结点，就进行于给定值的结点，就进行插入插入；n插入的原则插入的原则：若二叉排序：若二叉排序树为空树为空，则插入，则插入结点为树的结点为树的新根新根结点，否则继续在左子树结点，否则继续在左子树和右子树上查找，直至某个结点的左子树和右子树上查找，直至某个结点的左子树或右或右子树为空子树为空为止，则插入结点作为一个为止，则插入结点作为一个新的叶子新的叶子结点。结点。u 插入插入算法算法templateint BST:Insert(BinTreeNode *t,T&value) /在在以以t为根为根的二叉排序树中插入值为的二叉排序树中插入值为value的
77、结点的结点 if(t=NULL) t=new BinTreeNode(value); if (t=NULL) cout“Out of space”endl;exit(0); return 1; if(value data) Insert(t-GetLeft( ), value); /左孩子指针左孩子指针 else if(value t-data) Insert(t-GetRigth( ), value); /右孩子指针右孩子指针 else return 0; u 例：例：利用插入算法建立二叉排序树利用插入算法建立二叉排序树 53，68，55 ， 17 ，82，10，45535368536855
78、53685517536855178253685517821053685517821045对二叉排序树进行中序遍历可以得到有序序列对二叉排序树进行中序遍历可以得到有序序列n（1）被删除的结点）被删除的结点是叶子是叶子；n（2）被删除的结点）被删除的结点只有左子树只有左子树或者或者只有右只有右子树；子树；n（3）被删除的结点）被删除的结点既有左子树，也有右子既有左子树，也有右子树。树。可分可分三种情况三种情况讨论：讨论： 和插入相反，删除在和插入相反，删除在查找成功查找成功之后进行，并之后进行，并且要求在删除二叉排序树上某个结点之后，且要求在删除二叉排序树上某个结点之后，仍仍然保持二叉排序树的特性
79、。然保持二叉排序树的特性。4 4、二叉排序树的删除、二叉排序树的删除删除原则：删除原则：保持二叉排序树的特性。保持二叉排序树的特性。要删除二叉排序树中的要删除二叉排序树中的P结点，分三种情况：结点，分三种情况：nP为叶子结点为叶子结点nP只有左子树或右子树只有左子树或右子树nP左、右子树均非空左、右子树均非空 F F P PP PR RP PL L 二叉排序树的删除二叉排序树的删除P为为叶子叶子结点，只需修改结点，只需修改 P 双亲的指针双亲的指针： F-lchild=NULL F-rchild=NULL F P删除前删除前 F删除后删除后 二叉排序树的删除二叉排序树的删除P只有左子树或右子树
80、只有左子树或右子树nP只有左子树只有左子树，用，用P的左孩子代替的左孩子代替P (1)(2)SQPLP中序遍历：中序遍历：Q S PL PSQPL中序遍历：中序遍历：Q S PL(2)SPPLQ中序遍历：中序遍历：PL P S QSPLQ中序遍历：中序遍历：PL S Q(1) 二叉排序树的删除二叉排序树的删除P只有左子树或右子树只有左子树或右子树nP只有右子树只有右子树，用，用P的右孩子代替的右孩子代替P (3)(4)中序遍历：中序遍历：P PR S QSPRQ中序遍历：中序遍历：PR S Q(3)SPPRQ中序遍历：中序遍历：Q S P PRSQPR中序遍历：中序遍历：Q S PR(4)SQ
81、PRP 二叉排序树的删除二叉排序树的删除p左、右子树均非空左、右子树均非空n沿沿 P 左子树的左子树的根根 C 的右子树分支找到的右子树分支找到 S，S的右子树为空，将的右子树为空，将 S 的左子树成为的左子树成为 S 的双亲的双亲Q 的右子树，用的右子树，用 S 取代取代 p (5)FPCPRCLQQLSSL中序遍历：中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：中序遍历：CL C QL Q SL S PR F(5) 二叉排序树的删除二叉排序树的删除P左、右子树均非空左、右子树均非空n若若 C 无右子树，用无右子树，用 C 取代取代 P (6)FPCP
82、RCL中序遍历：中序遍历：CL C P PR FFCPRCL中序遍历：中序遍历：CL C PR F(6) 二叉排序树的删除二叉排序树的删除要删除二叉排序树中的要删除二叉排序树中的p结点，分三种情况：结点，分三种情况：nP为叶子结点，只需修改为叶子结点，只需修改 P 双亲双亲 F的指针的指针： F-lchild=NULL F-rchild=NULLnP只有左子树或右子树只有左子树或右子树nP只有左子树，用只有左子树，用P的左孩子代替的左孩子代替P (1)(2)nP只有右子树，用只有右子树，用P的右孩子代替的右孩子代替P (3)(4)np左、右子树均非空左、右子树均非空n沿沿 P 左子树的根左子树
83、的根 C 的右子树分支找到的右子树分支找到 S，S的右子树为空，将的右子树为空，将 S 的左子树成为的左子树成为 S 的双亲的双亲Q 的右子树，用的右子树，用 S 取代取代 P (5)n若若 C 无右子树，用无右子树，用 C 取代取代 P (6) 二叉排序树的删除二叉排序树的删除小结小结n二叉二叉排序树及其查找排序树及其查找n二叉排序树的插入、删除操作二叉排序树的插入、删除操作14.8 应用实例应用实例赫夫曼树赫夫曼树n 最优二叉树的定义最优二叉树的定义n 如何构造最优二叉树如何构造最优二叉树n 应用：赫夫曼编码应用：赫夫曼编码 n路径路径：从树中的一个结点到另一个结点：从树中的一个结点到另一
84、个结点之间的之间的分支分支构成这两个结点间的路径；构成这两个结点间的路径；n路径长度路径长度：路径上的：路径上的分支数目分支数目称为路径称为路径长度；长度；n结点的权结点的权：给树中结点所赋的具有物理：给树中结点所赋的具有物理意义的值；意义的值；n结点的结点的带权路径长度带权路径长度：从根到该结点的：从根到该结点的路径长度路径长度与该结点与该结点权权的乘积；的乘积；最优二叉树的定义最优二叉树的定义n树的带权路径长度树的带权路径长度= =树中所有树中所有叶子叶子结点的结点的带权路径之和；通常记作带权路径之和；通常记作 WPL= WPL= w wi i L Li i。n赫夫曼树（最优二叉树）赫夫曼
85、树（最优二叉树）：假设有：假设有n n个权个权值（值（w w1 1,w,w2 2, , , , w wn n），），构造构造有有 n n 个个叶叶子结点子结点的二叉树，每个叶子结点有一个的二叉树，每个叶子结点有一个 w wi i 作为它的权值，则作为它的权值，则带权路径长度最小带权路径长度最小的二叉树称为赫夫曼树。的二叉树称为赫夫曼树。最优二叉树的定义最优二叉树的定义n实例实例27 9 7549254WPL(T) = 7 2+5 2+2 3+4 3+9 2 =60WPL(T) = 7 4+9 4+5 3+4 2+2 1=89 最优二叉树的定义最优二叉树的定义n赫赫夫曼夫曼树树的构造的构造步骤步
86、骤n根据给定的根据给定的n n个权值个权值 w w1 1, w, w2 2, , w wn n ，构造构造n n棵只棵只有根结点的二叉树，令有根结点的二叉树，令其其权值为权值为w wj j；n在在森林森林中选取中选取两棵根结点权值最小的树两棵根结点权值最小的树分别分别作作为为左左右子树，构造一棵新的二叉树，置新二叉树右子树，构造一棵新的二叉树，置新二叉树根结点根结点权值权值为其左右子树根结点权值之和为其左右子树根结点权值之和；n在森林中在森林中删除删除这两棵树，同时将新得到的二叉树这两棵树，同时将新得到的二叉树加加入入森林中森林中；n重复上述两步，直到重复上述两步，直到森林中森林中只只剩剩一棵
87、树为止，这棵一棵树为止，这棵树即树即赫夫曼树赫夫曼树。如何构造最优二叉树如何构造最优二叉树n实例：实例：w=5,29,7,8,14,23,3,11w=5,29,7,8,14,23,3,1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100如何构造最优二叉树如何构造最优二叉树n赫夫曼编码赫夫曼编码（数据通信用的二进制编码数据通信用的二进制编码）用赫
88、夫曼树可以构造一种不等长的二进制编码，用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的并且构造所得的赫夫曼编码赫夫曼编码是一种最优前缀编码，是一种最优前缀编码，即使得所传即使得所传电文的总长度最短电文的总长度最短。 思想：思想：根据字符出现频率进行编码，使电文总根据字符出现频率进行编码，使电文总长最短。长最短。编码：编码：根据字符出现频率根据字符出现频率构造赫夫曼构造赫夫曼树树，然后，然后将树中结点引向其将树中结点引向其左孩子左孩子的的分支分支标标为为“0”“0”，引向其，引向其右孩子右孩子的的分支分支标标为为“1”“1”；每个字符的编码即为从；每个字符的编码即为从根根到每个到每个叶子
89、叶子的路径上得到的的路径上得到的0 0、1 1序列序列。最优二叉树的应用最优二叉树的应用赫夫曼编码赫夫曼编码例：例：试为这试为这5 5个字母设计不等长的赫夫曼编码，个字母设计不等长的赫夫曼编码，并给出该电文的总码数。并给出该电文的总码数。字母集a, b, c, d, e， 频率 5, 6, 2, 9, 7 最优二叉树的应用最优二叉树的应用赫夫曼编码赫夫曼编码9562752769767139527 赫夫曼编码赫夫曼编码95271629000167130111000110110111bedac 赫夫曼编码赫夫曼编码赫夫曼编码：赫夫曼编码： a 110 b 00 c 111 d 10 e 01电文总码数：电文总码数： 5*3+6*2+2*3+9*2+7*2=55小结小结n 最优二叉树的定义最优二叉树的定义n 如何构造最优二叉树如何构造最优二叉树n 赫夫曼编码赫夫曼编码n 树和二叉树的基本概念树和二叉树的基本概念n 二叉树二叉树n 树的存储结构及其与二叉树的转换树的存储结构及其与二叉树的转换n 二叉树的抽象类二叉树的抽象类n 二叉树的遍历二叉树的遍历n 树的遍历树的遍历n 二叉排序树二叉排序树n 赫夫曼树及其应用赫夫曼树及其应用 本章总结本章总结
