第6-树和二叉树.pptx
《第6-树和二叉树.pptx》由会员分享,可在线阅读,更多相关《第6-树和二叉树.pptx(158页珍藏版)》请在咨信网上搜索。
1、6.1树的定义和基本术语树的定义和基本术语6.2二叉树二叉树6.3遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4树和森林树和森林6.6哈夫曼树与其应用哈夫曼树与其应用树树(tree)是是n(n0)个个结结点点的的有有限限集集。在在任任意意一一棵棵非非空空树树中中:(1)有有且且仅仅有有一一个个特特定定的的称称为为根根的的结结点点;(2)当当n1时时,其其余余结结点点可可分分为为m(m0)个个互互不不相相交交的的有有限限集集T1,T2,Tm,其其中中每每一一个个集集合合本本身身又又是是一一棵棵树,并且称为根的树,并且称为根的子树子树。A只有根结点的树只有根结点的树ABCDEFGHIJKLM有
2、子树的树有子树的树根根子树子树数据对象数据对象D:D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。若若D为空集,则称为为空集,则称为空树空树。否则否则:(1)在在D中存在唯一的称为中存在唯一的称为根根的数据元素的数据元素root;(2)当当n1时,其余结点可分为时,其余结点可分为m(m0)个个互不相互不相交交的有限集的有限集T1,T2,Tm,存在,存在关系,关系,XiT1,其中每一棵子集本身又是一棵符合本定其中每一棵子集本身又是一棵符合本定义的树,称为根义的树,称为根root的的子树子树。数据关系数据关系R:ADT Tree基基 本本 术术 语语结点结点:结点的度结点的度:树
3、的度树的度:叶子(终端)结点叶子(终端)结点:分支分支(非终端非终端)结点结点:数据元素数据元素+若干指向子树的分支若干指向子树的分支结点拥有的子树数结点拥有的子树数树中所有结点的度的最大值树中所有结点的度的最大值度为零的结点度为零的结点度不为零的结点度不为零的结点DHIJM子孙子孙:以某结点为根的子树中的任一结点。以某结点为根的子树中的任一结点。ABCDEFGHIJMKL孩子孩子:结点的子树的根。结点的子树的根。双亲双亲:该结点称为孩子的双亲。该结点称为孩子的双亲。兄弟兄弟:同一个双亲的孩子之间互称兄弟。同一个双亲的孩子之间互称兄弟。祖先祖先:从根到该结点所经分支上的所有结点从根到该结点所经
4、分支上的所有结点有序树:有序树:子树之间存在确定的次序关系,不能子树之间存在确定的次序关系,不能互换互换无序树:无序树:子树之间不存在确定的次序关系子树之间不存在确定的次序关系树的深度:树的深度:树中结点的最大层次树中结点的最大层次堂兄弟堂兄弟:其双亲在同一层的结点其双亲在同一层的结点结点的层次结点的层次:假设根结点的层次为假设根结点的层次为1,若某结,若某结点在第点在第l 层,则其子树的根结点层次为层,则其子树的根结点层次为l+1DHIJMA AB BC CD DE EF FG GH HI IJ JK KL LM M结点结点A的度:的度:结点结点B的度:的度:结点结点M的度:的度:叶子:叶子
5、:结点结点A的孩子:的孩子:结点结点B的孩子:的孩子:结点结点I的双亲:的双亲:结点结点L的双亲:的双亲:树的度:树的度:结点结点A的层次:的层次:结点结点M的层次:的层次:树的深度:树的深度:320B,C,DE,FK,L,F,G,M,I,J3DE兄弟兄弟兄弟兄弟结点结点B,C,D为为结点结点K,L为为144堂兄弟堂兄弟结点结点F,G为为任何一棵非空树是一个二元组任何一棵非空树是一个二元组Tree=(root,F)其中:其中:root被称为根结点被称为根结点F被称为被称为m棵子树的森林棵子树的森林森林:森林:是是m(m0)棵互)棵互不相交的树的集合不相交的树的集合ArootBCDEFGHIJM
6、KLF树的其他表示形式:嵌套集树的其他表示形式:嵌套集合表示法、广义表表示、凹入表合表示法、广义表表示、凹入表示法。示法。DABCDEFGHIJMKL(A(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根例如例如:树的广义表形式树的广义表形式 Root(T)/求树的根结点求树的根结点查找类:查找类:Value(T,cur_e)/求当前结点的元素值求当前结点的元素值Parent(T,cur_e)/求当前结点的双亲结点求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子求当前结点的最左孩子RightSibling(T,cur_e)/求当前结点的右兄弟求
7、当前结点的右兄弟TreeEmpty(T)/判定树是否为空树判定树是否为空树TreeDepth(T)/求树的深度求树的深度TraverseTree(T,Visit()/遍历遍历基本操作基本操作P:P:InitTree(&T)/初始化置空树初始化置空树插入类:插入类:CreateTree(&T,definition)/按定义构造树按定义构造树Assign(T,cur_e,value)/给当前结点赋值给当前结点赋值InsertChild(&T,&p,i,c)/将以将以c为根的树插为根的树插入为结点入为结点p的第的第i棵子树棵子树 ClearTree(&T)/将树清空将树清空删除类:删除类:Destr
8、oyTree(&T)/销毁树的结构销毁树的结构DeleteChild(&T,&p,i)/删除结点删除结点p的第的第i棵子树棵子树对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素(无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)对比对比二叉树二叉树:或为空树,或是由一个或为空树,或是由一个根结根结点点加上两棵
9、分别称为加上两棵分别称为左子树左子树和和右子树右子树的、的、互不相交互不相交的二叉树组成。的二叉树组成。ABCDEFGHK根结点根结点左子树左子树右子树右子树特点:特点:(1 1)每个结点至多有二棵子树)每个结点至多有二棵子树(即不存在度大于即不存在度大于2 2的结点的结点);(2 2)二叉树的子树有左、右之)二叉树的子树有左、右之分,且其次序不能任意颠倒。分,且其次序不能任意颠倒。二叉树的五种基本形态:二叉树的五种基本形态:空树空树只含根结点只含根结点LRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树二叉树的主要基本操作二叉树的主要基本操作:Init
10、BiTree(&T);DestroyBiTree(&T);CreateBiTree(&T,definition);ClearBiTree(&T);BiTreeEmpty(T);BiTreeDepth(T);Assign(T,&e,value);Root(T);InsertChild(T,p,LR,c);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);DeleteChild(T,p,LR);PreOrderTraverse(T,Visit();InOrderTrave
11、rse(T,Visit();PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();二叉树的性质二叉树的性质性质性质1:在二叉树的第在二叉树的第i层上至多有层上至多有2i-1 个结点。个结点。(i1)证明:用归纳法证明之证明:用归纳法证明之i=1时,只有一个根结点,时,只有一个根结点,是对的是对的证明对任意的证明对任意的i命题成立,即第命题成立,即第i层上层上至多有至多有个结点个结点.假设假设第第i-1层至多有层至多有个结点个结点,二叉树二叉树每个结点的度至多为每个结点的度至多为2,所以所以第第i层上最大结点数层上最大结点数是第是第i-
12、1层的层的2倍,即倍,即故命题得证故命题得证性质性质2:深度为深度为k 的二叉树上至多含的二叉树上至多含2k-1 个结个结点(点(k1)。)。证明:证明:基于上一条性质,深度为基于上一条性质,深度为k 的二叉树上的二叉树上的结点数至多为的结点数至多为20+21+2k-1=2k-1。a1(1-qn)/(1-q)性质性质3:对任何一棵二叉树,若它含有对任何一棵二叉树,若它含有n0 个叶子个叶子结点、结点、n2 个度为个度为 2的结点,则必存在关的结点,则必存在关系式:系式:n0=n2+1。证明:证明:设设 二叉树上结点总数二叉树上结点总数 n=nn=n0 0+n+n1 1+n+n2 2又又 二叉树
13、上分支总数二叉树上分支总数 b=nb=n1 1+2n+2n2 2 而而 n=b+1=nn=b+1=n1 1+2n+2n2 2+1+1由此,由此,n n0 0=n=n2 2+1 +1。两类特殊的二叉树:两类特殊的二叉树:指的是深度为指的是深度为k且含有且含有2k-1个个结点的二叉树。结点的二叉树。123456789 10 11 12 13 14 15满二叉树:满二叉树:树中所含的树中所含的 n个结点和满二叉树中个结点和满二叉树中编号为编号为1 至至n 的结点的结点一一对应。一一对应。abcdefghij完全二叉树:完全二叉树:完全二叉树特点:完全二叉树特点:(1 1)叶子结点只可能在层次最大的两
14、)叶子结点只可能在层次最大的两层上出现层上出现;(2 2)对任一结点,若其右分支下子孙)对任一结点,若其右分支下子孙的最大层次为的最大层次为l,则其左分支下子孙的最,则其左分支下子孙的最大层次必为大层次必为l或或l+1+1。1231145891213671014151231145891267101234567123456性质性质4:具有具有n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。证明:证明:设完全二叉树的深度为设完全二叉树的深度为k 则根据第二条性质得则根据第二条性质得2k-1(第第k层第一个结点的编号)层第一个结点的编号)n 2k(第(第k1层第一个结点的
15、编号)层第一个结点的编号)即即 k-1 log2 n 1,编号为,编号为 i/2 的结点为其的结点为其双亲结点双亲结点;(2)若若2in,则该结点无左孩子,则该结点无左孩子,否则,编号为否则,编号为2i 的结点为其的结点为其左孩子结点左孩子结点;(3)若若2i+1n,则该结点无右孩子结点,则该结点无右孩子结点,否则,编号为否则,编号为2i+1 的结点为其的结点为其右孩子结点右孩子结点。归纳法证明:归纳法证明:1)i=1时,指的根结点,有时,指的根结点,有2=2*1是其左是其左孩子,孩子,3=2*1+1是根的右孩子;是根的右孩子;2)如果对于第)如果对于第k层的结点层的结点i,满足有左孩,满足有
16、左孩子为子为2i,右孩子,右孩子2i+1;123 i/2 2i+3ii+12i2i+1 2i+2对于对于i+1i+1这个结点,这个结点,i+1i+1的的左孩子为左孩子为2i+2=2(i+1),2i+2=2(i+1),右孩右孩子子2i+3=2(i+1)+1,2i+3=2(i+1)+1,成立成立114589126710123第k层i+1=2k2k-12k+1+12k+1第k+1层第第k层上最后一个结点的编号是层上最后一个结点的编号是2k-1,它的右孩它的右孩子是第子是第k+1层上最后一个结点层上最后一个结点,编号是编号是2k+1-1,右右孩子编号是它的双亲结点编号的孩子编号是它的双亲结点编号的(2
17、k-1)*2+1,左左孩子的编号是孩子的编号是(2k-1)*2所以,编号为所以,编号为i的结点的左孩子结点编号是的结点的左孩子结点编号是2i,右孩子结点编号是,右孩子结点编号是2i+1,双亲结点编号双亲结点编号 i/2 i=2k-12k+1-1=(2k-1)*2+1(2k-1)*2二叉树的存储结构二叉树的存储结构二、链式存储结构二、链式存储结构一、顺序存储结构一、顺序存储结构存储方式:存储方式:用一组地址连续的存储单元依次用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结自上而下、自左至右存储完全二叉树上的结点元素,点元素,即即将完全二叉树上编号为将完全二叉树上编号为i的结点元
18、的结点元素存储在一维数组中下标为素存储在一维数组中下标为i-1的分量中的分量中。一、一、二叉树的顺序存储结构二叉树的顺序存储结构对于一般二叉树,应将其每个结点与完全二对于一般二叉树,应将其每个结点与完全二叉树上结点相对照,存储在一维数组分量中,叉树上结点相对照,存储在一维数组分量中,“0”表示不存在此结点表示不存在此结点例如例如:125371234567891011121314012345678910111213140132646891011121314例如例如:ABCDEFABDCEF01234567891011121314013260表示不存在此结点表示不存在此结点00000000结点间关
19、系蕴含在其存储位置中;结点间关系蕴含在其存储位置中;浪费空间,适于存完全二叉树(在最坏浪费空间,适于存完全二叉树(在最坏情况下,深度为情况下,深度为k且只有且只有的单的单支树需要长度为支树需要长度为的一维数组)。的一维数组)。顺序存储结构特点:顺序存储结构特点:k个结点个结点2k-1AE二、二叉树的链式存储结构二、二叉树的链式存储结构(1 1)二叉链表)二叉链表(2)三叉链表三叉链表ADEBCF rootlchild data rchild结点结构结点结构:1.1.二叉链表二叉链表FABCDE在在n n个结点的二叉链表中,个结点的二叉链表中,有有n+1n+1个空指针域个空指针域typedefs
20、truct BiTNode /结点结构结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:ADEBCF root 2三叉链表三叉链表parent lchilddatarchild结点结构结点结构:ABCDEFtypedefstructTriTNode/结点结构结点结构TElemTypedata;structTriTNode*lchild,*rchild;/左右孩子指针左右孩子指针structTriTNo
21、de*parent;/双亲指针双亲指针TriTNode,*TriTree;parentlchilddatarchild结点结构结点结构:C语言的类型描述如下语言的类型描述如下:在二叉树的一些应用中,要求在树中在二叉树的一些应用中,要求在树中查找具有某种特征的结点,或者对树中全查找具有某种特征的结点,或者对树中全部结点逐一进行某种处理。提出部结点逐一进行某种处理。提出遍历遍历二叉二叉树的问题,树的问题,即按某条搜索路径巡访树中的即按某条搜索路径巡访树中的每个结点,使得每个结点均被访问一次,每个结点,使得每个结点均被访问一次,而且仅被访问一次而且仅被访问一次。遍历二叉树遍历二叉树“访问访问”的含义
22、可以很广,可以是对结的含义可以很广,可以是对结点作各种处理点作各种处理,如输出结点的信息等。如输出结点的信息等。“遍历遍历”是任何类型均有的操作,是任何类型均有的操作,对对线性结构线性结构而言,只有而言,只有一条搜索路径一条搜索路径(因为每个结点均只有一个后继因为每个结点均只有一个后继),故,故不需要另加讨论。而二叉树是不需要另加讨论。而二叉树是非线性非线性结构,每个结点可能有两棵子树,则结构,每个结点可能有两棵子树,则存在如何遍历即按什么样的搜索路径存在如何遍历即按什么样的搜索路径遍历遍历的问题。的问题。对对“二二叉叉树树”而而言言,可可以以有有三条搜索路径:三条搜索路径:1先上后下先上后下
23、的按层次遍历;的按层次遍历;2先左先左(子树)(子树)后右后右(子树)的遍历;(子树)的遍历;3先右先右(子树)(子树)后左后左(子树)的遍历。(子树)的遍历。若限定先左后右若限定先左后右,则只有则只有3种情况种情况先左后右的遍历算法先左后右的遍历算法先先(根)序遍历(根)序遍历中中(根)序遍历(根)序遍历后后(根)序遍历(根)序遍历根根LRABCDEFGHK类似于类似于送报纸送报纸若二叉树为空树,则空操作;否则,若二叉树为空树,则空操作;否则,(1)访问根结点;)访问根结点;(2)先序先序遍历左子树;遍历左子树;(3)先序先序遍历右子树。遍历右子树。先(根)序的遍历算法:先(根)序的遍历算法
24、:若二叉树为空树,则空操作;否则,若二叉树为空树,则空操作;否则,(1)中序中序遍历左子树;遍历左子树;(2)访问根结点;)访问根结点;(3)中序中序遍历右子树。遍历右子树。中(根)序的遍历算法:中(根)序的遍历算法:若二叉树为空树,则空操作;否则,若二叉树为空树,则空操作;否则,(1)后序后序遍历左子树;遍历左子树;(2)后序后序遍历右子树;遍历右子树;(3)访问根结点。)访问根结点。后(根)序的遍历算法:后(根)序的遍历算法:ADBCDLRADLRDLRBDCDLR先序遍历序列:先序遍历序列:ABDC先序遍历:根根 左左 右右ADBCLDRBLDRLDRADCLDR中序遍历序列:中序遍历序
25、列:BDAC中序遍历:左左根根 右右ADBCLRDLRDLRDADCLRD后序遍历序列:后序遍历序列:DBCA后序遍历:B左左 右右 根根-+/a*b-efcd先序遍历:先序遍历:中序遍历:中序遍历:后序遍历:后序遍历:-+a*b-cd/ef-+a*b-c d/e f-+a*b-cd/ef层次遍历:层次遍历:-+a a*b b-c cd d/e ef f先序遍历二叉树的递归算法描述先序遍历二叉树的递归算法描述StatusPreorder(BiTreeT,Status(*visit)(TElemTypee)/先序遍历二叉树先序遍历二叉树if(T)if(visit(T-data)/访问根结点访问根
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。