《数据结构课程知识点梳理汇总.docx》由会员分享，可在线阅读，更多相关《数据结构课程知识点梳理汇总.docx（26页珍藏版）》请在三一办公上搜索。
1、数据结构第一章:绪论1.概念：数据:所有能被计算机输入并且识别处理的符号的集合（数值性+非数值-视频,声音,图用数据元素:数据的基本单位.也叫记录数据项:数据的最小单位.EG-学生记录是数据元素,姓名,学号,性别是数据项.数据对象:具有相同性质的数据元素的集合.例如整数集合.*性质相同:具有相同类型和数量的数据项.数据类型:值+操作,三种:原子类型,结构类型抽象数据类型（ADT）ADT-抽象数据类型:抽象,与具体如何在计算机表示无关,用（数据对象,数据关系,基本操作集）定义.包括数行嗨关系,基本操作.*数据类型VS抽象数据类型:前者表示值+操作,例如c中整形,通常有厂家提供的已经实现的数据结构
2、,而后者表示数学模型+操作,仅仅取决于逻辑特性,于具体的实嬲7表示无关,只要其数学特性不变就不影响使用.-联系:本质相同,但是后者不局限于已经实现了的数据类型,还包括用户自定义的数据类型.一作用:ADT对用户透明（提供接口）,而不必了解实现细节.数据结构:具有一种或多种特定关系的数据元素的集合.包括三方面:逻辑结构,存储结构,数据运算.（算法的设计取决于逻辑结构,而算法的实现依赖于存储结构.）* 数据逻辑结构,数据元素,数据项在计算机中的映像为:存储结构,结点,数据域.* *数据运算=对数据定义的一组操作,定义在逻辑结构,实现依赖于存储结构.* -若逻辑结构相同,存储结构不同-数据结构不同*
3、-若逻辑结构相同&存储结构相同,但是运算不同-数据结构不同：EG:睇以物都相同,但是由于其运薪金不同称为不同的数据结构.-若逻辑结构相同,运算相同,存储结构不同-数据结构运算效率不同.数据结构评价准则：1.是否刻画了问题的基本特征.2.是否容易实现.选择数据结构考虑的因素：（存储时间量和空间量）：-A:TB:SA:包括:输入数据总量;编译时间;取指令执行时间;重复执行的次数.数据结构基本操作於力翻实现应用程序与存储程序的独立.数据结构研究内容:在非数值计算程序设计问题中,研究计算机的操您对家操作对象之间的走熬及其操作的学科.数据类型VS数据结构:前者可以看成是已经实现了的数据结构.并非所有数据
4、结构都具有插入,删除,查找三种运算,如栈和队列不具备查找.数据结构三要素：A:逻辑结构:线性+非线性：线性结构（一对一）：一般线性表+受限线性表（栈,队列）+推广线性表（数组,广义表）或者栈,队列,串,线性表）非线性结构:集合+树形结构（一般树,二叉树）（一对多）+图形结构（有向图,无向图）（多对多）更具体的分类:线性结构,集合树,图/网状结构.B:存储结构（物理结构）:数据元素的表示和关系的表示:（内存）顺序存储:优点:随机存取缺点:只能整块存储,外部碎片链式存储:优点:无碎片缺点:只能顺序存取,每个元素占用额外空间.索引存储:优点检索速度快缺点:索引表占用较多存储空间,修改索引表耗时.散列
5、存储:优点:检索,删除增加节点速度快.缺点:可能出现元素存储单元冲突,解决冲突增加开销.C:数据运算.逻辑结构vs存储结构：前者独立于后者,一种逻辑结构可以用多种存储结构.逻辑结构表示逻辑关系-数据元素的关联方式/辘关奏,存储结构是逻辑结构在计算机中的表示.数据结构研究的内容涉及三方面：1.数据如何组织2.数据如何存储3.数据的运算如何实现.2.算法:程序设计=算法+数据结构算法是对特定问题求解步骤的描述,计算机中是指令的有限序列,其中的指令表示一个/多个操作.算法具有以下5大特性：有穷性(在实际可接受时间内执行完成),确定性(没有歧义),可行性(可以通过已经实现的基本运算执行),输入(O-N
6、),输出(I-N).*算法满足有穷性,但是程序不一定满足(如OS监控程序),算法可以用计算机程序描述,但是不是说所有算法都必须用程序描述.*：算法设计输入参数设置为非引用型形参,输出参数设置为引用型形参.好的算法目标：正确性:正确的解决问题(对于非法输入能够满足规格说明的输出)可读性:容易理解健壮性:非法数据,合法反应效率&低存储量(花小钱,办大事)效率度量:时间复杂度:事前估计：频度:一个语句在算法中重复执行的次数,T(n)=Pindu.时间复杂度:T(N)的数量级=算法基本运算(最深层循环内的语句的频度)T(N)=O(f(n)影响因素:A:问题规模NB彳寺输入元素性质通常考虑最坏时间复杂度
7、.空间复杂度:算法耗费的内存空间Sn=O(g(n).算法所需解磔量占用的内存空间.原地工作:算法所需辅助空间是常量,OQ）计算方法:递归算法:由算法推出励飒懑闻求解.影响一个算法的时间效率主要因素:事先估计运行时间考虑因素：A:问题规模-待解决问题的数量B:算法执行的基本操作次数.算法VS存储结构：富病即雌网上好的存储结构可以提高算法效率.求解问题的步骤:建立ADT（运算描述）一设计合理的存储结构（运算实现）一设计算法数据运算与采用何种存储结构相关,算数/赋值/关系运算三类.算法的比较:两个算法上俄一般是采用平均时间复杂度,而一个算法分析通常采用孱妤时间复杂度.第二章:线性表1 .线性表：定义
8、:n个相同数据类型的数据元素的有限序列.可以为空.特点:线性性质:除了al,每个都有唯一的直接前驱,除了an,每个都有唯一的直接后驱.性质:个数有限,每一个元素占用空间相同,各元素排序有先后.线性表长度VS数组长度:前者是元素个数,后者是预先分配的存放线性表的存储空间的长度.前者小于等于后者.线性表VS一维数组:前者要求所有元素连续存储,后者不必.前者有就IW操作,后者为留行故元素.有序表:有一定Jl质序的线性表.2 .顺序表:线性表的顺序存储:采用数组存放元素C=ZPi(Ci)基本操作:插入操作(i=(1.n+1)平均移动n/2删除操作(i=(1.n)-平均移动(nl)2按值查找(i=(1.
9、n)平均比较次数(n+1)/23 ,顺序存储vs链式存储优缺点：顺序：存储密度大,内部物理地址相邻Iiiiiiiiiiiiiiiiiiiiiiiiiii储指针Iiiiiiiiiiiiiiiiiiiiiiiii储区域.存储空间秘邮筑随机读取或Jl质序读取适合于静态操作插入,删除移动将近一半元素一般用数组存储,实现容易可以折半查找-分配方式：静态:预先分配空间大小难以确定.动态:需要移动大量元素.查找才由入,删除T(N):链式：历解点物理地址不一定嬲无碎片现象,但是需要存储空间来存每个结点内占用一片用维存存储空间秘碑濠只能顺序读取适合动态如:删除元素,移动元素等动态操作方便运用于各种逻辑结构的存储
10、表示需要指针支持指针不可折半查找.分配灵活,高效.按值:无序-T=O(N)T=O(N)有序-T=0(1.0G2N)(折半查找)按序号:T=OQ)插入移动(ai-an=n-i+l个)i属于土刀删除移动(ai+l-an=n-i个)i属于。,用一比较:顺序访问所有结点:O(N)O(N)4 .为什么引入链式存储?-在插入删除操作以提高效率.5 .单链表;用头指针1.标识一个单链表,空表:1.=NU1.1.有头结点-头指针就等于-用头绿能循铲标说单链表,无头结点-用首结点指针标识.删除P结点后继结点T=O；判空(有头结点:1.TneXt=NU1.1.)头结点-目的:为了操作和运算上的方便头结点:数据域可
11、有可无,指针域-指向第一个元素结点.空表头结点指针域=NU1.1.头结点VS头指针：不管带不带头结点,头指针都是指向表中第一个结点，头结点是带头结点链表中的第一个结点.头结点优点:A:使得链表任何节点都有前驱结点,就礴A操作方猿和表其他位置操作一致；遍历:必须从头结点开始才能遍历整个表.B:无论链表是否空,头指针都是指向头结点的非空指针.如果含头结点任何插入都不合圜快结点指针的值6 .单链表:操作:1.头指针,s新的结点:(二表示赋值尸二表示判定)建立+查找+插入+删除：头插法(逆序H=O(N)代码:s-data=x;snext=lnext;lneXt=S 尾插法(增加一个尾指针r):T=O(
12、N)代码:S-data=x;rnext=s;r=s(r指针指向$即r指向新的表尾结点) 按序号直找:找到第i个结点为止：(含头结点XT=O(N)代码:1.nOde*p=1.-next初始化P指针;While(P&jvi)P=PTnext;j+Returnp;按值查找:T=C)(N)带头节点：代码:1.nOde*p=1.-next初始化P指针;While(P!=Null&pdata!=e)P=PTneXtretuenp; 插入操作:有P结点,节点b插入s结点.T=O(N)一将X插入第i个位置.代码:P=GETE1.EM(1.,i-l)找到第i个结点的前驱结点;STneXt=PTnext;pnex
13、t=s;注意:语句不可颠倒,试着自行分析.君姆S侬自m 删除结点:在p,q节点,节点c删除q节点T=O(N)-删除第i个结点.代码:P=GETE1.EM(1.,i-l)找到第i-1个结点的位置;PTneXt=q-nexree(q);求表长度:表的长度不将兴绿点-对于含头结点和不含头结点算法不同.7.双链表:插入删除结点算法T=C)(I)一为什么？-目比使德司以双向遍历,快速访问已知结点前后结点.-两个指针:PriOr,next与单链表区别:只是增加了一个Prior指针.双链表在插入删除过程中需要修改prior指针,关键在于:修改过程中不断链.与单链表相比,存储密度小.便于找到前驱,后继结点.A
14、:操作:在指定结点后进行操作: 插入:在P所指结点（结点*p）和结点C之间插入结点*s.T=O代码:snext=pnext;Pnextprior=s;S-Prior=p;pneXt=S关镇:.第一句第二句必须在第四句之前，试分析为什么?（否则:STneXt=S,s-prior=公 删除删除结点*p的后继结点*q：T=OQ）代E马:PTneXt=qnext;qnext-PriOr=p;nee（可以交换顺序）8彳盾环单链表:尾结点*r的next域指向1.一与单链表区别:表中最后一个节点指针域不是NU1.1.,而是揭娱结点一特点:表中无NU1.1.节点;判空条件（有头结点）:买结点励韵溟百等型指针-
15、设尾指针:对于表头,尾操作T=O（I）.一不带头节点判空:1.=NU1.1.;尾结点:PTneXt=1.-从表中任意节点都可以遍历整个链表.9 .循环双链表：区别:头结点的Prior指针指向表尾.-判别条件:尾结点*p-p11ext=1.;空袭头结点的PriMneXt均等于1.（1.next=1.-prior=1.）10 .静态链表：一借助数组描述线性表的链式存储结构.一与链表区别:指针是结点的相对地址（数组下标）一作用:适用于没有指针的高级语言中.-特点插入删除同动态链表,只需改指针,不用移动元素.无嬲苴的瘫难以确定表长.11 .表的合并算法：n,m长度的有序表利用二朝琥法合成一个有序表,T
16、=5h）11V.12 .总结:各种表操作T荟萃:T=O(X)顺序表:操作在于承勃元素链式结构:操作在于艇!J第i；个结点的修顺序:红色为修正参考答案.顺序表,带头结点单链表,带头结点循环单链表,不带头结点只有尾指针循环单链表,带头结点双链表,带头结点循环双链表.A:查找第i个元素(i=Q,n):X=1.N,N,N,N,N.C:插入新兀素作为第一个兀素:X=N,1.1.1.1.1E:插入第i个元素:(i=(2,n):X=I(N),N,N,N,N,N.G:删除最后一个元素：X=1.N,N,N,N,1B:查找第一个值为X的元素：X=N,N,N,N,N,N.D:插入新元素作为最后一个元素:X=IzNz
17、NzIzNzIF:删除第一个元素：X=I(N),1.1.1.1.lH:删除第i个元素:(i=(2,n)X=I(N)lNzNzNzNzN.13 .注意事项:时间复杂度:插入操作主要是查找丽茂点删除操作主要是再找两节点&修改指针域.Ji质序表和链表访彻旗续扁B是:r=o仞15.在双链表删除一个结点(非尾结点)需要修改2个指针域日亩入则需要4个指针域.16时间复杂度:Cn(from2n)n!.分析最不适合的存储结构唯一的方法:时间复杂度.17根据指针的连接方式,链表分为:静态链表,(动态)链表.栈,队列栈1.栈:只允许在一端进行插入删除操作的线性表.一概念阚先用麟的一勰栈底:固定的另一端.一特点后来
18、居上后进先出（1.IFo）.一基本操作:POP（出栈）,Push（压栈）,GETT0P（获取栈顶元素）- 栈的插入-压樗栈的删除一嫂- -应用实例撤销功能-例如Word,excel,网页浏览器.- 理解:A:是一个线性表,元素有前驱后继关系.B:最先进栈的不一定只能最后出栈-元素的糊悯谢敏但是必须是浅质元素出栈.2植的存储结构:- 顺序存储:用数组存储元素，链栈:规定:为头续点所有操作在同成必须附设一个栈顶指针（默认指向元素际0位置.单链表头进行.A:栈空:top=-l;一个元素:top=。优点:便于多栈共享空间提高效率.B栈顶指针:S.top,栈顶元素:SdataStop.c初始化:top=
19、r-表示指针指向栈顶元素.进栈操作:若栈不满TT指针加一-一然后入值.1.链栈选择:最好:带头结点单链表带头结点双链表VS不头循环单链表.-选择:带头单.-先声明变量开拓空间,后赋值.出栈:获取栈顶元素-栈顶指针减一.D7=0a-判别条件:删除是否栈空?,读栈顶.插入-是否栈满?进栈代码:ifSztop=Maxsize-1.returnerror;S.top+;1.判空:t。P=NUIl5如匕51：=0.(或者5如匕+5上=6.2.入栈:进入一个m结点值为I：出栈代码：-m.data=I;mnext=S.top;ifs.top=-lzreturnerror;x=S.dataS.top;Stop
20、.S.top=mtop指向m;Scount+.（或者合并为:x=S.dataStop-D占.wE:几种栈顶指针变化：（想象栈底有一空元素被栈顶指针指向）.count.3.出栈:变量X存放要删除的结x=S.dataS.top;k=S.top;S.top=S.topnext;free(k);S-两大Jl质序/链栈对比：顺序栈：链栈：1.要事先确定空间.1.灵活1栈空:topl=-l,2栈空top2=Maxsi乙2.存取定位方便.2.额外开若初始化栈顶指针为top=-1.指针指向栈顶，4.T=0Q）以上操作.如果初始化top=0,表指针指向栈顶下一个元褰相应的操作也要变化.F:共享栈:要求:两个相同
21、数据类型的栈，&并且需求呈现相反的关系.两端栈底.数组下标范围：0-MaXSiZe-1.销栈满:top2=topl+1.（两个指针相邻时）3.不会栈满操作:进栈:topi指针加一,进栈，-元素变化大-链栈,反之顺序栈.top2指针减一,进栈.一算法关键判断是对栈1还是栈2进行操作.3.顺序栈的实现:用数组data0,Max-1,0作为栈底,Max-I作为栈顶,也可以反之,，旦建注意不能将中间位置作为栈底或栈顶.4栈的作用&应用：-栈的作用:为什么有了顺序表和链表还要栈呢？一术业有专攻,栈可以使我们更专注于入栈,出栈的操作,不必过多关心与实际问题无关的例如数组下标增减的问题,不必考虑过多无关细节
22、.简化了程序设计问题,划分了不同的关注层次,使得思考范围缩小,更加聚焦于我们要解决的问题.一栈的应用:递归:一个回教自己潮昭己.函数调用时,系统用栈保存必要的信息.系统为调用者构造一个活动记录,包括参数表和返回地址,并将记录压入栈中,若有局部变量,也压入.递归VS迭代：递归造巽吉构,易理解,简洁-大量的递归耗费大量时间和内存.（重复计算）迭代彳盾环结构,不需要占用额外内存.4.进栈为a,b,c,d=出栈不可能为d,c,a,b.队列1.队列：逻辑结构：一定义:只允许在双尾的一端进行施,在以头进行硼辘作的受限线性表.一特点FIFo-先进先出.一队头:允许删除的一端;队尾允许插入的一端.-操作入队:
23、EnQUeUe;出队:DeQUeUe;判别是否队空:QUeUeEmpty.-不可以读取队列中间的某个数据.-生活实例操作系统队列机制溶服系统犍盘打字,缓冲区.2.存储结构:一顺序存储：-定义:一维数组存储,设置两个指针：rear和front指示队尾和队头，点据efront指向以头元素，空:Q.front=N3I&Q.rear=NuII指向队尾个元素3.-初始状态:Q.rear=Q.front=0.-队空:Q.rear=Q.front-镯卜表尾插入,表头删除.1.链队:本质有队头队尾指针的弱蹦头指针指向队头结点房指针以尾结-进队:若队不满TT先入队-T队尾指针+1.Iiiiiiiiiiiiiii
24、iiiiiiiiiiiiiiiiiii总是在链头一出对：Iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii若队不空TT取队头元素一一队头指针+：next=s;-当Q.rear=Max.size,有可能队伍不满,存在一个元素的情况,而此时并为满.-假雌现象:当rear加到队尾后在往后才next);就会出现数组越界,产生溢出，4 .总是将链队设为带头结点舔T蚱.4:单链表实现队列,链队头位置.便于删除.5 .入队:如上图3:sdata=e;snext=nubQ.rearQrear=s.6 .出队:判定队空？m=Q.frontnext;s=*(Q.front-Q.frontTnex
25、t=Q.frontTnext-next;free(m).然而此时数组并没有满.4.循环队列.rearfront，I116113115下标：01234循环队列VS链队列：P1：定义首尾相接的队列的财存碣纬与1.时间上:T=O一作用:解决周溢故限循环队列需要事先申请,链队申请,释放一操作:-除法取余.节点有微小的.时间开销.- 初始Qrear=Q.front=0;2.空间上彳盾环队列长度固定,浪费空间- 队头指针+l:Q.front=(Q.front+l)%Maxsize链队列不存在,灵活.- 队尾指针+IQrear=(Q.rear+l)%Maxsize- 队列长度(Q.rear+Maxsize-
26、Q.front)%Maxsize总结:1.确定-循环队列,反之链队列.一问题:当Qrear=Q.front:一可以表示队列为空,但是此时也可以表示队列满了,怎么区分？- 办法:三种：A:牺牲一个单元，以队头指针在队尾指针的下一位置作为队满的标识.- 队满条件圈(Q.rear+l)%Maxsize=Q.front- 队空条件:Q.rear=Q.front.- 队列元素个数Qrea+Maxsize(表示第几圈的尾巴)-Qfront.个数二=(Qrear+Maxsize-Q.front)%Maxsize-考虑不够减的情况.B:增加表示元素个数的成员,队空:Q.size=0,队满:Q.size=MaX
27、SiZe-都有Q.front=Q.rear.C:类型中增设tag成员tag=0,如果因为删除导致(5.什0讨=(3.r由,空;反之当tag=l,满.着重第一种:操作代码:加宁Q.rear,考虑在队尾巴插入时状态.1 初始化:Qfront=Qiear=O2 .判空:Qfront=Q.rear3 .入队:先判满?一入队一指针加一.-if(Q.rear+l)%Maxsize=Q.frontzreturnfalse;Q.dataQ.rear=x;Q.rear=(Q.rear+l)%MaxsizeJ考虑在最后插入.4.出队:空?-取值-指针加一.-if(Q.rear=Q.front)zreturnfal
28、se;a=Q.dataQ.front;Q.front=(Q.front+l)%MaxsizeP2:公式小结:此时:front指向队头rear指向队尾的下一个元素.队头指针+IQfront=(Q.front+l)%Maxsize-队尾指针+l:Q.rear=(Q.rear+l)%Maxsize-队列长度(Q.rear+Maxsize-Q.front)%Maxsize.可以认为是左右两边之和.-A21表示最多21个,从0-20.2最适合用作链队的:带首尾指针的非循环单链表.3.最不适合用作链队的:带首指针的非循环双链表.栈VS队1.实际应用:一般二者都是拿来存放临时数据的,如果先保存的先处理一队列
29、,如果后保存的先处理-一栈.2.例如:后进先出:括号匹配问题-栈.3.队列:先进先出:0S中作业排队问题.4栈的应用:-A:括号匹配问题：-B:表达式求值:后缀表达式ABCD-*EF-相应的中缀表达式:A+B*(C-D)-EF-区别:中缀包含括号和操作数,后缀包含操作数与操作符,已经考虑优先级,无括号.后缀表达式与原来的中缀表达式的后序遍历异曲同工.一过程：A,B,CQ,进栈遇到-,CQ出栈运算C-D=rl,进栈rl,以此类推.-C:递归应用:递归:函数调用它自身精髓将原始问题转化为属性相同但规模较小的问题.-借助栈将递归算法转换为非递归算法.5.队列的应用：-A:层次遍历保存下一步的处理Jl
30、厕学.永远是第一个节点出队入队左右孩子,如果只有左孩子,进入左孩子.B:计算机系统中的应用：-Sl:主机&外设速度匹配问题-设置打印缓冲区.-S2:资源竞争问题-请求时间先后顺序排队获取资源.矩阵压缩存储:1.数组：定义:n个相同类型数据元素构成的有限序列(n=l).n称为:维度,也就是n维数组.-操作初始化,销毁,存取元素,修改元素.2 .数组VS线性表：一数组是线性表的胸;一维数组可以看为线性表,二维数组是线性表的线性表.3 .压缩存储:修勰维=j-下三角地区),那么aij下标为：当i=j,S=l+2+i-l+j-l减一是因为数组下标为0=i*(i-l)2j-l.当i=j,S=i*(i-l
31、)2+j-l.当i=i-n+n-i+2+j-i+l-l=(i-l)*(2n-i+2)2+j-i.当ji,k=n*(n+l)2+l-l=n*(n+l)2.- -P3:三对角矩阵:三线形状:当岛城惇晶J25卷所以:S下标=(i-l-2+l)*3+2+(2+j-i)-l=2i+j-3其中i=n,j=n,i-jv=1.j-i=0)一非空树要求A只有1个根节点.B:当N1,其余节点分为m个互不交的有限集合,每个集合又是一颗树,称为根节点的子树.一树的定义是递归的n个结点有n-1条边.一树的用处:表示层次结构的数据.- 概念:度:子节点个数.树的度:树中节点的最大度数.叶子结点:度为0的结点.内部节点:除
32、了根节点的分支结点.分支结点:度大于O的结点.结点深度:从根节点自上而下.结点高度:从叶结点自下而上.树的高度(深度):树的最大层数.祖先:从根节点到结点之间的分支上的所有节点.堂兄弟:双亲在同一层的结点.- -有序树:子树左右不能交换,有顺序无序树:反之.- -路径:两个节点之间所经过的结点朝恒上而力.路径长度:路径的边的个数.- -森林:m(m=0)颗互不相交的树的集合.S2:性质:常用结论Xr表示大于等于X的最小整数.一树的结点数=所有结点的度+1.一度为m的树中,第i层最多以一I个结点(i=l).- -高度为h的m叉树至多有瓣中拿个结点.- -具有n个结点的m叉树最小高度为:。(*卜)
33、，7)一树结构特点:根节点唯一,无双亲;叶结点无孩子;中间结点:一个双亲/多个孩子.53 .度为4,高度为h,至少:h-3个结点n个结点,度为4,至少高度=n-3.54 .树的路径长度:从树根到每一个结点的路径长度总利55 .树根到每一节点的路径最大值:h-1.P2:二叉树:1.属于树,特点：- 每个结点至多2个孩子.(磔妥为2,并且左右子树有次应不可颠倒.- 二叉树和树都属于树形结构,但二叉树不是做勤务- 就像人的左右手,二叉树就算一个节点只有一棵树也要区分左右.2 .定义:A:n个(n=0)结点的有限集合.-要么是空二叉树,要么由一个根节点+不相交的左右子树组成.-解析:二叉树可以为空,但
34、是二O是有国政3 .二叉树VS度为2的有序树的区别：-A:二叉树可以为空.B:有序的不同:二叉树的有序是确定的,不是侬宁另一个续点即使只有一个孩子节点,也要区分顺序;而后者有序是当有2个孩子节点时,左右有序.4 .特殊的二叉树：-A4m班宸义:所有分支结点都有左右子树,并且所有叶子结点都在同一层上.编号为i,左孩子2,右孩子2i+l;双亲:图般妫2n个结点(n属于奇数)其父节点叶子结点:(n+l)/2;分支结点:(n-l)/2.-满m叉树:i的双亲结点姑TM2丽k：*w岛&V笳t光至&三年等詈1nk7.dlk=1)- C:高度为H的二叉树至多:2八H-I(H=1)- D:具有N个结点的(N0)
35、完全二叉树高度为:专同随刈/%电有第修/is1今遨i里前嚏rA1log?”n。=1+27E:结点i（编号）所在的层次（深度）为:1“（用上述D类比记忆）.F:n个节点二叉树高度范围:胸随到n.G:高度为h的完全二叉树节点个数范围畲一川普f（第h层至少1.至多满）H:一个完全二叉树共有n个节点,那么叶结点个数为怎ii,ll.上二叉树若只有度为0,2的节点,那么当高度为h,结点数至少:2h-l.J：高为h,度为m的树结点数最少:h+m-l,最多:满m叉树即可.M:含n个结点的不同形态二叉树为:卡特兰数.S:正则K叉树（度为0/K）的最少结点（h层）Xh-l）*K+lG.万能公式:二叉树解题办法:设
36、度为0,1,2的结点为NO,N1,N2个,N2+1=NO,即可.特别的,对于满二叉树,度为1的只可能是lfO个.-对于m叉树,一般通用公式.5 .二叉树的顺序存储：一数组:用一组地址连续的存储单元依次自上而下,自左而右存储完全二叉树上的节点元素,然后用一些方法指明父子关系.- -先至二O加健二月履合崛存嬉因为节点序号唯一反应了节点之间的逻辑关系,又可以利用下标确定位置,节省存储空间.- -一般二叉树:添加空节点表示关系最坏情况:高度H,只有H结点二叉树需要占据2人H-1个存储单元.（二2八H-I-H（空0处）+H（个元素）.- -注意:二叉树顺序存储:数组下标表示结点编号+节点之间的关系- -
37、通常数组下标从1开始一一对应.树的Jl质序存储:数组下标只表示结点编号,下标上存的内容反应关系- -二叉树都可以用树的存储结构存储,反之不然6 .二叉树的链式存储：-三部分左指针域IChild,右指针域rchild,数据域data.又是可以增加为三叉链表.一在含有n个节点的二叉链表中有n+1个交酸侬(2n-(n-l)=n+l).7 .二叉树的遍历&线索二叉树：-A:二叉树的遍历:按某条路径访问全部节点,使得每个结点有且只被访问一次.- 本质:对二叉树这种非线性结构进行线性化操作.- B:遍历次序:N-根节点,1.-左子树,R-右子树.先序N1.R,中序1.NR,后序1.RN(序指的是根节点的先
38、后顺序/位置都是T=O(N).-EG:先序遍历:算法:先序-PreOrder,中序-InOrder,后序-POStorder.VoidPreorder(BiTreeT)IfT!=NullVisit(T);访问根节点.Preorder(TIChiId);PreOrder(T-rchild);- -结果:产生一个先序序列.- C:二叉树应用：-递归算法与非递归算法之间的转换.-层次遍历-利用队列,根节点入队出队,访问结点有左子树进队有右子树,进队出队,对出对结点访问反复.-由遍历序列构造二叉树：施如内总展宾枷知道层次就知道根节点)雁定二叉树,先后,先层则不能唯一确定.(考虑abc,cba序列).一
39、原因:先为根节点,后序逆序为根节点,中依次分成左右结点,以此类推.一方多先中序:每次找到根节点,钮冷割左右序列才安照根节点分配即可.中序:序列第一个节点:最左下角;序列最后一个节点:最右下角.-后序遍历作用:交换二叉链表所以分支结点的左右子树位置.-已知先序,后序顺序,问哪个中序不符合-逆向根据先序,中序是否可以得出后序?-二叉树:先序与中序相同的条件:只有右子树.-二叉树先序与中序相反-二叉树所有节点无右子树.一二叉树先序与后序相同只有根节点;相反-高度等于节点个数.-完全二叉树:已知结点总数就可以确定形态.所以已知任何一种序列（如先序）就行.一后序遍历:作用:找到从祖先到孙子的路径.-后序
40、遍历:n在m前条件:n为m子孙.&-若中序,a在b前,那么:a在b左边.D:稣二-定义:利用传统二叉链表中的空指针存放结点的前驱,后继指针,方便应用二叉树操作算法.将二叉树按照某吸院遍索化的过程.一本质:是一种物理线前是加上线索后的链表结构.- 目的:加快直找结点前驱和后继的速度.- 超定1二叉树线索化规定:若无左子树,令Ichild指向其前驱节点;若无右子树,令rchild指向其后继节点,并且增加两个标志域表明当前是指向其孩子还是前驱节点.（等于O表示指向孩子,反之指向1表示前马0后继）.- 线索链表:以上述结点构成二叉链表的存储结构成为线索链表.- 线索:指向节点的前3口后继指针叫做线索.
41、- 线索二叉树:加上线索的二叉树.一线索化:对二叉树以淼姒摩遍历使其变为线索二叉树的过程.实质:就是:遍历二叉树,检查左右节点指针域是否为空（也就是是否有左右子树）,为空则加上线索.-n个节点线索二叉树上含有的线索为（N+1）个.-Sl:中序线索二叉树的构造有时为了方便,在二叉树的线索链表加上一分笺点并且让他的Ichild指向根节点,rchild指向中序遍历访问的最后一个节点.同时让中序第一个节点Ichild和最后一个节点rchild都指向头结点-=建立双向线索链表.可以双向遍历.一中序线索二叉树主要是为了运算服务的,这种遍历不再需要借助栈,因为他的节点中隐含了线索二叉树的前驱和后继信息.E:
42、树的存储结构：一后续线索二叉树的遍历必须借助栈的支持,不能解决求后序的后继问题.-三种方法：Wl:双亲表示法:指针指示其双亲节点在数组中的位置.一特点:可以很快得到双亲节点,但是求结点的孩子需要遍历整个结构.W2:孩子表示法:将每个节点的孩子用单链表连接起来,需要N个单链表.一特点：可以很快得到孩子节点,但是求结点双亲需要遍历整个结构.W3:孩子兄弟法:又名:二支核表示法指向结点第一个孩亍的指针,指向节点下一个兄弟的指针.一特点:可以方便的将树转化为二叉树,易于查找孩子.但是:查找双亲节点比较麻烦.F:树,二叉树,森林的转换:二叉树转换为树/森林是哙-的兄蒜多-树转化为二叉树：一左孩子,右兄弟,无右子树.一T画法:三步走:Sl:兄弟间画长线;S2:只保留每个结点的第一个孩子节点连劣S3:顺时针选择45度.-森林转化为二叉树：一挨个转化,依右边放置.-T画法:三步走:Sl:根节点之间连线;S2:每棵树转化为二叉树;S3:绕第一棵树旋转45.G:树和森林的遍历：一树的遍历:先根遍历,后根遍历.-先根遍历=对应二叉树的先序遍先后根遍历=对应二叉树的不原遍方一森林的遍历:先序,中序遍历：-先序遍历=对应二叉树的先岳遍比中序遍历=对应二叉树的中原遍比-层次遍历：树的层次序列不磁匚叉树的层次序列.
