树二叉树二叉树的遍历树森林与二叉树的转换树和森林的遍ppt课件.ppt
( 4.5 )《树二叉树二叉树的遍历树森林与二叉树的转换树和森林的遍ppt课件.ppt》由会员分享，可在线阅读，更多相关《树二叉树二叉树的遍历树森林与二叉树的转换树和森林的遍ppt课件.ppt（126页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n树树n二叉树二叉树n二叉树的遍历二叉树的遍历n树、森林与二叉树的转换树、森林与二叉树的转换n树和森林的遍历树和森林的遍历n树的应用树的应用第六章 树和二叉树Chapter 6 Tree and Binary Tree经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用6.1 树一、树的定义一、树的定义树是树是n(n0）个有限数据元素的集合。当）个有限数据元素的集合。当n=0时称时称这棵树
2、为空树；否则，任意一棵非空树必符合以下两这棵树为空树；否则，任意一棵非空树必符合以下两个条件：个条件：n树中有一个特殊的数据元素称为树的根结点，根结点树中有一个特殊的数据元素称为树的根结点，根结点没有前驱结点；没有前驱结点；n若若n1，除根结点外的其余结点可分为，除根结点外的其余结点可分为m（m0)个个互不相交的有限集合互不相交的有限集合T1,T2,T3,，Tm，其中每一个集，其中每一个集合合Ti本身又是一棵树，称之为根的子树。本身又是一棵树，称之为根的子树。ADCBEFGHI经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接
3、受服务的费用Tree逻辑结构n树的根结点没有前驱结点，除根结点外的所有树的根结点没有前驱结点，除根结点外的所有结点有且只有一个前驱结点。结点有且只有一个前驱结点。n树中所有结点可以有零个或多个后继结点。树中所有结点可以有零个或多个后继结点。分支关系、层次关系、一对多的非线性辑结构。二、树的基本术语二、树的基本术语（1）结点的度结点的度：结点所拥有的子树的个数。：结点所拥有的子树的个数。（2）叶子结点：叶子结点：度为度为0的结点。的结点。（3）分枝结点：分枝结点：度不为度不为0的结点。的结点。（4）树的度：树的度：树中各结点度的最大值称为该树的度。树中各结点度的最大值称为该树的度。（5）孩子、兄
4、弟、双亲：孩子、兄弟、双亲：树中一个结点的子树的根结点树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它的孩子结点称为这个结点的孩子。这个结点称为它的孩子结点的双亲。具有同一个双亲的孩子结点互为兄弟。的双亲。具有同一个双亲的孩子结点互为兄弟。（6）结点的层数：结点的层数：规定树的根结点的层数为规定树的根结点的层数为1，其余结点，其余结点的层数等于它的双亲结点的层数加的层数等于它的双亲结点的层数加1。（7）树的深度：树的深度：树中所有结点的最大层数称为树的深度。树中所有结点的最大层数称为树的深度。（8）有序树和无序树：有序树和无序树：如果一棵树中结点的各子树从左到如果一棵树中结点的各子
5、树从左到右是有次序的，即若交换某结点各子树的相对位置则右是有次序的，即若交换某结点各子树的相对位置则构成不同的树，称这棵树为有序树；否则为无序树。构成不同的树，称这棵树为有序树；否则为无序树。（9）森林：森林：零棵或有限棵不相交的树的集合称为森林。零棵或有限棵不相交的树的集合称为森林。ADCBEFGHI经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用4.树的基本操作树的基本操作1 1、初始化（、初始化（、初始化（、初始化（initiate(t)initiate(t)）2 2、求指定结点所在树的根结点、求指定结点所
6、在树的根结点、求指定结点所在树的根结点、求指定结点所在树的根结点(root(x)(root(x)3 3、求指定结点的双亲结点、求指定结点的双亲结点、求指定结点的双亲结点、求指定结点的双亲结点(parent(t,x)(parent(t,x)4 4、求指定结点的某一孩子结点、求指定结点的某一孩子结点、求指定结点的某一孩子结点、求指定结点的某一孩子结点(child(t,x,i)(child(t,x,i)5 5、求指定结点的最右边兄弟结点、求指定结点的最右边兄弟结点、求指定结点的最右边兄弟结点、求指定结点的最右边兄弟结点(rightsibling(t,x)(rightsibling(t,x)6 6、将
7、一棵树插入到另一树的指定结点下作为它、将一棵树插入到另一树的指定结点下作为它、将一棵树插入到另一树的指定结点下作为它、将一棵树插入到另一树的指定结点下作为它 的子树的子树的子树的子树(insert(t,x,i,s)(insert(t,x,i,s)7 7、删除指定结点的某一子树、删除指定结点的某一子树、删除指定结点的某一子树、删除指定结点的某一子树delete(t,x,i)delete(t,x,i)8 8、树的遍历树的遍历树的遍历树的遍历(tranverse(t)(tranverse(t)遍历：按某种方式访问树中的每个结点，且每个遍历：按某种方式访问树中的每个结点，且每个遍历：按某种方式访问树中
8、的每个结点，且每个遍历：按某种方式访问树中的每个结点，且每个结点只被访问一次。结点只被访问一次。结点只被访问一次。结点只被访问一次。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用四、树的存储结构四、树的存储结构双亲表示法双亲表示法孩子表示法孩子表示法孩子兄弟表示法孩子兄弟表示法双亲孩子表示法双亲孩子表示法经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26
9、 G 5序号序号data parent 1.双亲表示法双亲表示法 typedef struct elemtype data;int parent;nodetype;nodetype tMAXNODE;data parent#define MAXNODE 100结点结构结点结构:C语言的类型描述语言的类型描述:typedef struct elemtype data;int parent;int son;int next;nodetype;特点：便于实现特点：便于实现parent(t,x)和和root(x)操操作作,难于实现难于实现child(t,x,i)和和rightsibling(t,x)操
10、作操作改进后的结构改进后的结构经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用2.孩子表示法（多重链表法）孩子表示法（多重链表法）ABCDEFGHIJABC DE F G H I J两种方法：两种方法：结点的指针域的个数结点的指针域的个数=树的度。树的度。同构型同构型结点的指针域的个数结点的指针域的个数=结点的度结点的度异构型异构型同构型同构型经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用ABCDEFGHIJtypedef str
11、uct TreeNodetypedef struct TreeNodetypedef struct TreeNodetypedef struct TreeNode int data;int data;int data;int data;struct TreeNdoe*SonMAXSON;struct TreeNdoe*SonMAXSON;struct TreeNdoe*SonMAXSON;struct TreeNdoe*SonMAXSON;nodetype;nodetype;nodetype;nodetype;异构型异构型孩子表示法孩子表示法 c c语言描述语言描述(同构型同构型)3.双亲双亲
12、-孩子表示法孩子表示法ABCDEFGHIJJ 4A 0B 1C 1D 1E 2F 2G 3H 4I 4234891056712345678910序号 data parent将双亲表示与孩子将双亲表示与孩子表示结合起来表示结合起来经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 AB C E D F G4.孩子兄弟表示法（二重链表法）孩子兄弟表示法（二重链表法）typedefstructtreenodeelemtypedata;structtreenode*son;structtreenode*next;nodet
13、ype;BDACEFG经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 6.2 二叉树一、二叉树的基本概念一、二叉树的基本概念(1)定义：二叉树是一个由定义：二叉树是一个由n(n0）个有限元素构成的集）个有限元素构成的集合，这个集合或者为空，或者合，这个集合或者为空，或者是由一个称为根的元素及两个是由一个称为根的元素及两个互不相交的、分别被称为左子互不相交的、分别被称为左子树和右子树的二叉树组成。当树和右子树的二叉树组成。当二叉树中元素个数二叉树中元素个数n=0时，称时，称为空二叉树。为空二叉树。n在二叉树中，一
14、个元素也称作在二叉树中，一个元素也称作一个结点。一个结点。ABGDCHEF二叉树经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用二叉树的五种不同形态二叉树的五种不同形态注意：注意：二叉树与树的区别二叉树与树的区别:(1)二叉树是一个有序树，而树二叉树是一个有序树，而树是无序树。是无序树。(2)二叉树的度小于等于二叉树的度小于等于2。=树经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用二叉树（4）特殊的二叉树n满二叉树一棵深度为一棵深
15、度为h且有且有2h-1个结点个结点的二叉树。的二叉树。对树中结点按从上到下、从左到对树中结点按从上到下、从左到右的顺序进行编号。右的顺序进行编号。abdcefhijgklmno8910 11121314 154567231经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n完全二叉树ACGFBDEHIJ除第除第除第除第h h层外，其它各层层外，其它各层层外，其它各层层外，其它各层(1(1 h h-1-1)的结点数都达到的结点数都达到的结点数都达到的结点数都达到最大个数，第最大个数，第最大个数，第最大个数，第h h层
16、从右向层从右向层从右向层从右向左连续缺若干结点，这左连续缺若干结点，这左连续缺若干结点，这左连续缺若干结点，这就是完全二叉树。就是完全二叉树。就是完全二叉树。就是完全二叉树。若二叉树的深度为若二叉树的深度为若二叉树的深度为若二叉树的深度为h h，且共有，且共有，且共有，且共有n n个结点。对树中结个结点。对树中结个结点。对树中结个结点。对树中结点点点点按从上到下、从左到右的顺序进行编号，若编按从上到下、从左到右的顺序进行编号，若编按从上到下、从左到右的顺序进行编号，若编按从上到下、从左到右的顺序进行编号，若编号为号为号为号为i(1in)i(1in)的结点与满二叉树编号为的结点与满二叉树编号为的
17、结点与满二叉树编号为的结点与满二叉树编号为i i的结点的结点的结点的结点位置相同，则此树称为完全二叉树。位置相同，则此树称为完全二叉树。位置相同，则此树称为完全二叉树。位置相同，则此树称为完全二叉树。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用显然，一颗满二叉树一定是一颗完全二叉树显然，一颗满二叉树一定是一颗完全二叉树1234567891011234567891非完全二叉树非完全二叉树非完全二叉树非完全二叉树经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购
18、买商品的价款或接受服务的费用n二叉排序树45628849181230302582若为非空二叉树，根若为非空二叉树，根结点的左子树所有结结点的左子树所有结点的关键字值都小于点的关键字值都小于根结点关键字值，右根结点关键字值，右子树所有结点的关键子树所有结点的关键字值都大于或等于根字值都大于或等于根结点关键字值。左子结点关键字值。左子树和右子树又分别是树和右子树又分别是一棵二叉排序树。一棵二叉排序树。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n平衡二叉树平衡二叉树ACEFBD平衡因子：二叉树任意结点的左子树深度
19、减去右子树平衡因子：二叉树任意结点的左子树深度减去右子树深度的差值，为此结点的平衡因子。深度的差值，为此结点的平衡因子。平衡二叉树：二叉树中每个结点的平衡因子的绝对值平衡二叉树：二叉树中每个结点的平衡因子的绝对值都不大于都不大于1，则称这棵二叉树为平衡二叉树，则称这棵二叉树为平衡二叉树.2345691平衡二叉树平衡二叉树非平衡二叉树非平衡二叉树经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用性质性质性质性质1 1 若二叉树的层次从若二叉树的层次从若二叉树的层次从若二叉树的层次从1 1开始开始开始开始,则在二叉树的
20、则在二叉树的则在二叉树的则在二叉树的 第第第第 i i 层最多有层最多有层最多有层最多有 2 2i-1 i-1 个结点。个结点。个结点。个结点。(i i 1)1)二、二、二叉树的性质二叉树的性质证明：证明：i=1 i=1 时，有时，有2 2i-1 i-1 =2 20 0=1=1，成立，成立假定假定 ：i=k i=k 时性质成立；即有时性质成立；即有2 2k-1k-1个结点个结点.当当 i=k+1 i=k+1 时，第时，第k+1k+1的结点至多是第的结点至多是第k k层结点的层结点的两倍，即总的结点个数至多为两倍，即总的结点个数至多为2222k-1 k-1=2 2k k故命题成立故命题成立经营者
21、提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用性质性质性质性质2 2 高度为高度为高度为高度为k k的二叉树最多有的二叉树最多有的二叉树最多有的二叉树最多有 2 2k k-1-1个结点个结点个结点个结点.(.(k k 1)1)证明：仅当每一层都含有最大结点数时，二叉树证明：仅当每一层都含有最大结点数时，二叉树的结点数最多，利用性质的结点数最多，利用性质1 1可得二叉树的结点数可得二叉树的结点数至多为：至多为：2 20 0+2 21 1+2 22 2+2 23 3+2 2k-1 k-1=2 2k k 1 1 经营者提供
22、商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用性质性质性质性质3 3 对任何一棵二叉树对任何一棵二叉树对任何一棵二叉树对任何一棵二叉树,如果其叶结点个数为如果其叶结点个数为如果其叶结点个数为如果其叶结点个数为 n n0 0,度为度为度为度为2 2的非叶结点个数为的非叶结点个数为的非叶结点个数为的非叶结点个数为 n n2 2,则有则有则有则有 n n0 0n n2 21 1证明：证明：1 1、结点总数为度为、结点总数为度为0 0的结点加上度为的结点加上度为1 1的结点再加上度的结点再加上度 为为2 2的结点：的结点：n=n
23、n=n0 0+n+n1 1+n+n2 22 2、另一方面，二叉树中一度结点有一个孩子，二、另一方面，二叉树中一度结点有一个孩子，二 度结度结 点有二个孩子，根结点不是任何结点的孩子，因此，点有二个孩子，根结点不是任何结点的孩子，因此，结点总数为：结点总数为：n=n n=n1 1+2n+2n2 2+1+13 3、两式相减，得到：、两式相减，得到：n n0 0=n=n2 2+1 +1 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用性质性质4 具有具有n个结点的完全二叉树的高度个结点的完全二叉树的高度 为为 log2
24、n +1证明：设完全二叉树的高度为证明：设完全二叉树的高度为h h，则有，则有 2 2h-1h-1-1 -1 n n 2 2h h-1 -1 2 2h-1h-1=n n 2 2h h 取对数取对数 h h 1 log 1 log2 2(n n)1,1,则则则则 i i 的双亲为的双亲为的双亲为的双亲为 i i/2/2 (i 1)i 1)/2/2 )n n 若若若若2*2*i i=n)n)，i i无无无无左孩子；左孩子；左孩子；左孩子；n n 若若若若2*2*i i+1=+1+1 n)n)，i i无无无无右孩子；右孩子；右孩子；右孩子；经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加
25、赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用四、二叉树抽象数据类型四、二叉树抽象数据类型n数据集合：结点集合数据集合：结点集合n操作集合：创建二叉树操作集合：创建二叉树左插入结点左插入结点右插入结点右插入结点左删除子树左删除子树右删除子树右删除子树遍历二叉树遍历二叉树一、二叉树的存储结构1.顺序存储结构ACGFBDEHIJ0123456789ABCDEFG HIJ6.3二叉树的设计和实现二叉树的设计和实现完全二叉树的顺序存储完全二叉树的顺序存储经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 二叉 遍历 森林 转换 ppt 课件
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内