2025年数据结构高效复习知识点全兼容攻略

《数据构造》期末复习

复习要点：

第一章

1.有关基本概念：数据、数据元素（基本单位）、数据项（最小单位）、算法

及其特性等；

◎数据：所有能输入到计算机中并被计算机程序处理的符号总称。

◎数据元索：基本单位。

◎数据项：最小单位。

◎算法特性（5点）：有穷性；确定性；可行性；输入；输出。

2.逻辑构造、存储构造（物理构造）及其类型；

◎逻辑构造有四种基本类型：集合、线性构造、树形构造和网状构造。

◎数据元素之间的关系有两种不一样的表达措施：次序映象和非次序映象.

并由此得到两种不一样的存储构造：次序存储构造和链式存储构造，

◎注：期中考题目

数据构造分为两大类，即为逻辑构造和存储构造。其中逻辑成果又分为线性构

造和非线性构造，存储构造一共有四把（次序、链接、索引、散列）。

3.算法分析：语句频度（执行次数）计算、时间和空间复杂度分析。

表达措施

◎语句频度：直接写次数。

◎时间复杂度：0（执行次数），如：0（n）o

◎空间复杂度：0（所需空间）

第二章

1.丞序表（数组）插入、删除、有序表合并算法及其移动次数计算；

1213212428304277

数据兀素

序号12345678

表达L.clem[0][1：[2][3][4][5][6][7]

◎次序表插入

算法思想：假如要在序号5前插入元素e,需要将序号5〜8向后移动一种

位置。

▲移动次数为4次，公式n-i+l

StatusListInsert_Sq(SqList&L,inti,ElenTypee)

〃在第i个元素前插入新元素e,当前i力5

(

if(i<111i>L.length+1)returnERROR;〃1值不合法

if(L.length>=L.listsize)〃当前存储空间已满，增加分配

<

ElenType*newbace=(ElenType*)realloc(L.elen,

(L.listsize+LISTINCREMENT)*sizeof(EleeT卯e));

iF(fneubace)returnERROR;

L.elen=newbace;

L.listsize+=LISTINCREMENT;

}

ElenType*p;

ElenType*q=&(L.elem[i-1]);〃序号5对应L

For(p=&(L.elem[L.length-1]);p>=q;-p)

〃表依「length值为8,p指向序号8,对应L.elem"]

*(P♦1)=*P；〃元素后移

*q=e；〃序号5对应L.elee[4]赋值为e

++L.length;

returnOK;

>

◎次序表删除

算法思想：假如要删除序号5元素，需要将6〜8依次向前移动一位

▲移动次数为3次，公式ni

StatusListDelete_Sq(SqList&L,inti,ElemType&e)

〃删除第i个元素，并用e返回其值，当前i为5

<

if(i<1||i>L.length)returnERROR;〃1值不合法

ElenType*p=&(L：elem[i-1]);〃p为被删除元素祇置

e=*P；〃被删除元素的值赋宿给e

ElenType*q=L.elem+L.length-1;

〃表尾元素佥置L.elem[G]〃，为L.elem[7]

For(++p;p<=q;++p)

〃P先移到序号6；判断是查处于q

*(P-1)=*P；〃元素前移

—L.lpngfrh;〃表长减1

returnOK：

◎有序表合并

LA=(3,5,8,H)

LB=(2,6,8,9,11,15,20)

则LC=(2,3,5,6,8,8,9,11,11,15,20)

算法思想(以非递减为例)：La和Lb非递减排列，La与Lb中元素逐一比较，较小

的先插入Lc中。

▲注：非递减是指递增排序，但元素有也许相等，与之相对的有非递增排序。

▲移动次数为(La.length+Lb.length)

uoidMergeList_Sq(SqListLa,SqListLb,SqList&Lc)

<〃算法2.7一

//己如顺序线性表La剂Lb的元素按值非递减排列。

〃归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列。

ElenType*pa,*pb,*pc,*pa_last,*pb_last;

pa=La.elem;pb=Lb.elem;

Lc.listsize=Lc.length=La.length+Lb.length;

pc=Lc.elem=(ElenType*)nalloc(Lc.listsize*sizeof(ElenType));

〃pc指向lc.elem[G]

if(?Lc.elem)

exit(OUERFLOW);〃存储分配失败_

palast=La.elen♦La.length-1;〃pa_last揖向La最后一个兀鎏

pb_last=Lb.elpn♦Lb.length-1;〃pb_last指向Lb最后一1个元素

while(pa<=palast&&pb<=pblast)<//归并

iF(*pa<=*pb)*pc++=*pa++;

〃如果pa当前值小于pb当前值，pc当前位置的值赋值为pa当前值

else*pc++=*pb++;

>_

while(pa<=pa_last)*pc++=*pa++;//眄入La的剩余匹塞

while(pb<=pb_last)*pc++=*pb++;//插入Lb的剩余元素

〃这两个whi1e语句只会执行其中一个

>//MerqeList

2.链表（有无头节点、单双、循环）插入（前、后）、删除（前、自身、后）的指针挂接、

建立（不带头节点）算法。

◎单链表

▲每个节点有数据域和指针域datanext

m

头ala2a3a4a5a6

带头节点L-/—---------------f----------*一

Pt

ala2a3a4a5a6

不带头节点L-----—,-----,-----*-----*-----*—

Pt

口

单循环链表

•在P(a3)节点前插入S节点

(DQ=P；//先让Q指向a3

(2)P=L;//P指向第一种节点(带头结点指向头结点，不带头结点指向al)

(3)while(P->next!=Q)P=P->next;//找到a3的前驱a2,P指向a2

(4)S->next=P->next;//P->next为a3,让S->next等于a3

(5)P->next=S;〃a2指针域指向节点S

・在P(a3)节点后插入S节点

(l)S-next=P->next;

(2)P->next=S:

・删除P(a3)前一种节点

(DQ=P；

(2)P=L;

(3)while(P->next->next!=Q)P=P->next;〃找到al

(4)P->next=P->next->next;//让al指针域指向a3,从而删除a2

・删除P(a3)节点

(DQ=P；

(2)P=L;

(3)while(P->next!=G)P=P->next;〃找到a2

(4)P->next=P->next->next;//让a2指针域指向a4,从而删除a3

・删除P(a3)后一种节点

(l)P->next=P->next->next;//让a3指针域指向a5,从而删除a4

◎双链表

▲每个行点有前驱指针、数据域、后继指针priordatanext

双循环链表

头ala2a3a4

•在P(a2)节点前插入S节点

▲技巧：先让S->prior和S->next与链表建立关系

注：环节(4)必须在环节⑶背面

(l)S->next=P://先让S->next指向a2

(2)S->prior=P->pricr;〃S-〉prior指向al

(3)P->prior->next=S;//再把al->next指向S

(4)P->prior=S;//a2->prior指向S

•在P(a2)节点后插入S节点

注：环节⑷必须在环节⑶背面

(l)S->prior=P;

(2)S->next=P->next;

(3)P->next->prior=S;〃a3->prior指向S

(4)P->next=S;

・删除P(a2)前一种节点al

(1)Q=P->prior;〃6指向要被删除的al;

(2)P->prior=P->pricr->prior;〃P->priro指向头

(3)P->prior->next=F;〃头->next指向P

(4)free(Q);〃释放al的存储空间

・删除P(a2)节点

(1)P->next->prior=p-〉prior;

(2)P->prior->next=p->next;

(3)free(P);

・删除P(a2)后一种节点a3

(1)Q=P->next;

(2)P->next=P->next->next;//a2—>next指向a4

(3)P->next->prior=F;//a4->prior=P

(4)free(Q);〃释放a3存储空间

◎建立(不带头节点)单链表

voidCreateList_L(LinkList&L,intn)〃建立不带头结点链表

LinkListpvq;

For(inti=0;i<n;++i)

p=(LinkList)nalloc(sizeoF(LNode));

cin»p->data;〃输入数据墩

p->next=NULL;〃P当前为最后一个节点

if(i==0)〃第一个节点

L=P；

q=p;

continue;〃不执行后面的语句

q->next=p;〃让前一个节点next指针指向p

q=p;〃q指向p

Ltqtpt

IZI

Ltqtpt

第三章

1.栈的进出序列、栈、队列、循环队列的满/空条件；

▲由于栈的插入、删除操作是限制在栈顶进行的，因而后进栈的元素必然是先出栈，

0.因此栈是“后进先出”表。

▲由于队列的输入、输出操作分别在队的两端进行，因此先入队的元素必然先输

出，故队列又称为“先进先出”表

◎栈的进出序列

例题：进栈序列为123,也许得到的出栈序列是什么？

答:共五种123/132/213/231/321

进出栈状况（以132序列为例）：

1进栈-*1出栈，输出If2进栈一3进栈一3出栈一2出栈输出32

◎栈、队列、循环队列的满/空条件

栈空条件：s.top=s.base;栈满条件:s.top-s.base=stacksize;

队空条件:Q.front=Q.rear;队满条件:q->rear-q->front=MAXSIZE

循环队列空条件：Q.front=Q.rear

循环队列满条件：为防止在队满是队头指针和队尾指针也是重叠的状况，规定队列

中

尚有一种空的存储单元时为队满,即为Q.front=（Q.rear+l）M0Dmaxsize（MOD为取

余

运算符）。因而，这种循环队列不适合用动态数组作为存储构造。

2.栈、队列的存储构造、基本操作算法（双向栈）；

◎栈存储构造

・次序栈

typedefstruct{

SElemType*base;

SElemType*top:

intstacksize;

}SqStack;

・锌式栈

IIT栈底

◎队列存储构造

・次序存储构造

出队列入队列

图3.8队列的示意图

Q.front

Q-rear

Q.front

drear

(c)

012M-1

IT0IT

栈i底栈i顶栈2顶栈2底

存储构造：

typedefstruct{

Elemtype*base|2];

Elcmtypc*top[21；

JBDStacktype;〃双向栈类型

初始化：

StatusInit_Stack(BDStacktype&tws.intm)〃初始化种大小为m的双向栈tws

(

tws.base[0]=(Elerntype*)maIloc(sizeof(Elemtype)*in);

tws.basc[l]=tws.basc[0]+m;

tws.top[0]=tws.base[0];

tws.top[IJ=tws.base[I];

retuniOK:

}//Init_Stack

入栈：

Statuspush(BDStacktype&tws,inti.Elcmtypcx)

//x入栈,i=0表达低端栈,i=1表达高端栈

if(tws.top[0]>tws.top[l])returnOVERFLOW;

〃注意此时的栈满条件

if(i==0)*tws.top[0]++=x;

elseif(i==1)*tws.top[1]—=x;

elsereturnERROR;

returnOK;

}//push

出栈：

Statuspop(BDStacktypc&tws,inti,Elcmiype&x)

//x出栈,i=0表达低端枝,i=l表达高端栈

{

if(i==0)

(

if(tws.top[0]=tws.base(OJ)returnOVERFLOW;

x=*-tws.top[0];

)

elseif(i==I)

(

if(tws.top[l]==tws.base[l])returnOVERFLOW;

x=*++tws.top[l];

}

elseretuniERROR;

returnOK;

}〃pop

第四章

1.字符串模式匹配的简朴算法；

intIndex(SStringS,SStringT,intpos)

{//算法4.5

//返回子串T在主串S中第pos个字符之后的位置。

//若不存在，则函数信为0。

//其中，T非空，IWpos这StrLength(S)。

inti=pos;

intj=1;

while(i<=S[0]&&j<=T[0]){

if(S[i]==T[j]){//继续比较后继字符

++i；

++j：

)

else{//指针后退重新开始匹配

i=i-j+2;〃此时i为上次开始比较位置的下一位

j=1；

)

}

if(j>T[0])returni-T[O];

elsereturn0;

}〃Index

2.计算NEXTo

j：1234567

串：abcabaa

next[j]：0111232

▲技巧：第一二个肯定是0,1!假如要计算next[4],找的字符串必须是以第3个字

符c为结尾，第1个字符a为开头的。

以第6个为例，a前一种字母是b,以第5个字符b为结尾的ab刚好和以第1个字符为

开头的ab匹配，因此next[6]=2+1=3。

第五章

1.二维数组的地址(下标)换算；

习题5.1假设有二维数组A6*8,每个元素用相邻的6个字节存储，存储器按字节

编址。已知A的起始存储位置(基地址)为1000,计算：

(1)数组A的体积(即存储量)

6*8*6=288字节

(3)按行存储是，元素al4的第一种字节的地址

1000+(8*1+4)*6=1072

基址+(每行的元素个数*行数+目前列序)*每个元素所占存储单元

(4)按列存储时，元素a47的第一种字节的地址

1000+(6*7+4)*6=6276

基址+(每列的元素个数*列数+目前行序)*每个元素所占存储单元

习题5.2假设按低卜标优先存储整数组A9*3*5*8时，第一种元素的字节地址是

100,每个整数占四个字节。问下列元素的存储地址是什么？

(2)allll地址：100+(3*5*8*1+5*8*1+8*1+1)*4=776

(3)a3125地址：100+(3*5*8*3+5*8*1+8*2+5)*4=1784

(4)a8247地址：100+(3*5*8*8+5*8*2+8*4+7)*4=4416

2.特殊矩阵(三角、其他有规律)压缩为一维的下标计算:;

◎下三角矩阵压缩为一维数组(记忆公式)

▲技巧：推荐把公式(2)背下来<i,j.R范围都是从0开始)，其他根据范围变化公

(1)若1<=」，j<=n,0<=R<=n(n+l)/2-1

当i>=j时，k=i(i-l)/2+j-l;

当i〈j时，k=j(j-l)/2+i-l.

(2)若0<=i,j<=n-l,0<=R<=n(n+l)/2-1

〃注意i,j是0到n-l,下面的公式相称于把⑴中i变成i+1,j变成j+1

当i>=j时，k=(i+1)i/2+j;

当j<j时,k=(j+l)j/2+i.

(3)若l<=j,j<=n,K=R<=n(n+l)/2

〃注意R是1到n(n+l)/2,下面公式相称于把(1)中k变成k-1

当i>=」时，k=i(i-l)/2+j;

当i<j时，k=j(j-l)/2+i;

(4)若0<=j,j<=nT,K=R<=n(n+l)/2

当i>=」时，k=(i+l)i/2+j+l;

当i<j时，k=(j+l)j/2+i+l;

3.稀疏矩阵的三元组表达。

由5.10T的三元俎表b&d*

4.稀疏矩阵应用的算法。(略)

第六章

1.二叉树的性质：

性质1：在二叉树的第i层上至多有2"个结点(i21)。

性质2：深度为k的二叉对至多有2*—1个结点(kNl)o

性质3：对任何一棵二叉树T,假如其终端结点数为n(),度为2的结点数为n2,则

n0=n2+lo

性质4：具有〃个结点的完全二叉树的深度为［I，3，“十1。

性质5：假如对一棵有n个结点的完全二叉树的结点按层序编号，

则对任一结点i(lKiKn),有：

(1)假如i=l,则结点i是二叉树的根，无双亲；

假如i>l,则其双亲是Li/2」。

(2)假如2i>n,则结点i无左孩子：

假如23n,则其左孩子是2i。

(3)假如2i+l>n,则结点i无右孩子；

假如2i+l«n,则其右孩子是2i+l.

2.二叉树的先序、中序、后序、层次遍历过程；树的光序、后序、层次遍历过程；

b

先,遍历：-+a♦b-cd/ef

中仔遍a+b*c-d-e/f

QJ产遍为：abcd-*+ef/-

乂次遍历:-+/a*efb-cd

二叉树遍历过程：

先（根）序遍历：根一左子树一右子树

中（根）序遍历：左子树一根一右子树

后（根）序遍历：左子树一右子树一根

层次遍历：从上到下，从左往右，逐一遍历

树的遍历过程：

先根（次序）遍历：先访问根结点，然后依次先根遍历根的每棵了•树（根一

子树）

后跟（次序）遍历：先依次后根遍历每棵子树，然后访问根结点（子树一

根）

层次遍历：从上到下，从左往右，逐一遍历

▲注：树与二叉树互相转化后

树的先根遍历相称于二叉树的先序遍历

树的后根遍历相称于二叉树的中序遍历

3.给出两个遍历序列，画出树（二叉树、树）

习题6.23画出和下列已知序列对应的树T：

（1）树的先根次序访问序列为GFKDAIEBCIIJ;

（2）树的后根次序访问序列为DIAEKFCJUBGo

注：树的后根遍历相称于二叉树的中序遍历

①由⑴知G为根：

⑵G为根,联络⑵知G无右子树；

③观测（1）,F为G左子树；

④根据③：观测（2）知DIAEK在F左

边,

CJHB在F右边；

⑤观测⑴,K为F左子树：

⑥根据⑤，观测⑵知K无右子树；

⑦观测（1：,D为K左子树：

⑧根据⑦，观测⑵知D无左子树：

⑨观测（1；,A为D右子树;

⑩观测（2）,IE分别为A左右子树；

F的右子树自行观测判断。

4.二叉树与树互相转换；

◎树转化成二叉树：

规则：树的最左孩子变成二叉树左子树,该左孩子的兄弟变成二叉树左子树的右子树

注：原树中B为A最左孩子，C,D为B兄弟，变成二叉树后C成为B右子树，D成为C

右子树。

◎二叉树转化成树

5.求哈夫星树和给出编码、带权途径长度计算。

习题6.26假设用于通信的电文仅由8个字母构成，字母在电文中出现的频率分别

为0.07,0.19,0.02,0.06,0.32,0.21,0.10。试为这8个字母设计哈夫曼编码，并求

带权途径长度

设这8个结点为A、B、C、I）、E、F、G、H,其对应的权为7、：9、2、6、32、3、21、10。

①目前未用权：7、19、2、6、

32、3、21、10,选出2、3构造

出5。

⑵目前未用权：7、19、6、32、

21、10、5,选出5、6构造出

IK

③目前未用权：7、19、32、

21、10、11,选出7、10构造出

17。

④目前未用权：19、32、21、

11、17,选出11、17构造出

23。

⑤目前未用权：19、32、21、

▲编码：树的左分支为0,右分支为1。

得到哈夫曼编码为A:1101B:01C:lllllD:1110E:10F:11110G:00H:1100

带权途径长度：(7*4+19*2+2*5+6*4+32*2+3*5+21*2+10*4；/100=2.61

▲注：该公式为：A途径长*A权+B途径长*B权+…+H途径长*H权，由于设的权值是

本来的100倍，因此成果除以100。

第七章

(a)有向图G”(b)无向图G注：以有向图G1为

例(有途径用L否则

no1010-

■0110-0)

10101

0000vlv2v3v4

Gl.arcs=,G2.arcs=01011vl

00010110

10100v20000

J000_

JO1100.v30001

图7.8图的邻接矩阵

注：以有向图GI为例

标号0123

00110

1(1000

20001

31000

inlIQ|A第0行值为1的是1、2,因此有

qFiTTVl-2-lo

第1行值全为0,因此有

V2o

TT第2行值为1的是3,因此有

V3-3o

03|A第3行值为1的是0,因此有

V4-0

1o|Ao

2~Q]A

2A

(a)Gi的邻接表；(b)G：的邻接表;(0G)的逆邻接表

2.求最小生成树(Prim、Kruskal)：

①从VI开始，找到最个边

(VI,V3)：

②寻找与VI、V3有关联的最小

边，找到(V3,V6)：

③寻找与VI、V3,V6有关联的最

小边，找到(V6,V4)；

④寻找与VI、V3、V6、V4有关联

的最小边，此时有(V4,V1)和

(V3,V2),由于(V4,VI)与本来的

边构成圈，因此选择(V3,V2)。

(假如(V4,VI)不与本来的边沟成

圈，则二条边任选一条)；

⑤寻找与VI、V3、V6、V4、V2有

◎克鲁斯卡尔（Kruskal）（避圈法）：以边为基础

措施简介：依次寻找权最小边，防止生成一种圈，所有点联通时生成最小树。

3.拓扑排序：

环节：（1）在有向图中选一种没有前驱的顶点且输出之。

（2）从图中删除该顶点和所有以它为尾的弧。

©®

V\V1匕I

®

VA*

—

0®@

%W⑴

(a)(b)(c)(e)

输出：V6VIV4V2V5

注：拓扑排序不唯一。

4.求最短途径过程(Dijkstra、Floyd)0

◎迪杰斯特拉(Dijkstra)

习题7.11试运用Dijkstra算法求题7.11图中从顶点a到其他各顶点间的最短途径,

写

出执行算法过程中各步状态。

求解过程:

终点S

bcdefg

(终点集)

15212

K=1(a,c}

(a.b)(a.c)(a,d)

1512106

K=2

(a,b)(a,d)(a,c.e)(a.c,f)

15111016

K=3{a»c.f»e}

(a,b)(a,c,f.d)(a,c,e)(a»cJ,g)

151116

K=4{a,c,f,e,d)

(a.b)(a.c,f.d)(a«c«f(g)

1514

K=5(a«c*f*etdg)

*(a,b)(a.c.f.d.g)t

15

K=6U»c,f,e,d.g,b}

.(a,b)

K=1时，找a能直接抵达的点，有b,c,d,(a,c)权最小，(a,c)为a到c最短途

径，将c放如终点集S：

K=2时，找a能直接抵达的点，或通过(a,c)能抵达的点，(a,c,f)权最小，(a,c,f)

为a到f的最短途径，将f放入终点集S；

K=3时，找a能直接抵达的点，或通过(a,c)能抵达的点，或通过(a,c,f)能抵达的

点，

(a,c,e)权最小，(556)为己到6最短途径，将e放入终点集S；

K=4时，找a能直接抵达的点，或通过(a,c)能抵达的点，或通过(a,c,f)能抵达的

点，或通过(a,c,e)能抵达的点，(a,c,f,d)为a到d最短途径，将d放入终点集S：

K=5时，找a能直接抵达的点，或通过(a,c)能抵达的点，或通过(a,c,f)能抵达的

点，或通过(a,c,e)能抵达的点，或通过(a,c,f,d)能抵达的点，(a,c,f,d,g)权最小，为a

到g最短途径，将g放入终点集S：

K=6时，只剩余(a,b),(a,b)为a到b最短途径，将b放入终点集S。

◎弗洛伊德(Floyd)

图7.36带权有向图

(a)有向网G，(b)邻接矩阵

D(。)D<n02)

D

012012012012

004110411046046

1602602602502

23oo0370370370

p(-l)p(0)p(l)p⑵

P

012012012012

0ABACABACABABCABABC

1BABCBABCBABCBCABC

2CACACABCACABCACAB

图7.37图7.36中有向图的各对顶点间的最短路径及其路径长度

注：是从Vi到Vj的中间顶点的序号不不小于1的最短途径的长度;D(k)

[i][j]是从Vi到Vj的中间顶点的序号不不小于k的最短途径的长度；D(n-l)[i][j]就是

从Vi到Vj的最短途径的长度。

D(1)栏中，Vi不容许有转折点。直接填邻接矩阵。

D(0)栏中，Vi-*V'j只容沪通过V0转折，或者不转折。通过V0转折权值不不小于原权

值，就把原权值替代掉。

D(D栏中，Vi-Vj只容访通过VO、VI转折，或者不转折。假如转折后权值不不小于

原权值，替代。

D(2)栏中，Vj-V」容许通过V0、VI、V2转折，或者不转折，假如转折后权值不不小

于原权值，替代。此时p(2)中就是各点间的最短途径。

第九章

1.如下所有查找成功平均查找长度

2.次序查找：折半查找：

◎次序查找：从表中最终一种记录开始，逐一进行比较。

▲平均查找长度

等概率时,平均查找长度ASL=(n+l)/2

不等概率时，ASL=nFl+(n-l)P2+…+2Pn-l+Pn

◎折半查找：

指针low和high分别指示待查元素所在范围的下界和上界：mid=(low+high)/2,

假如要找的值不小于S[mid],则让mid=(mid+1+high)/2,继续比较：

假如要找的值不不小于S[nid],则让mid=(low+mid-1)/2,继续比较。

▲平均查找长度

n+1

----lo6g?Z

等概率条件下，ASL=n(n+l)-l

当n>50时，有近似成果ASL1°g2(n+l)T

3.二叉排序树的插入(建立)、删除、平衡过程：

◎二叉排序树建立

(1)若它的左子树不空，则左子树上所有结点的值均不不小于它的根结点的值：

(2)若它的右子树不空，则右了•树上所有结点的值均不小于它的根结点的值；

(3)它的左、右子树乜分别为二叉排序树。

习意9.9@已知如下所示长度为12的表

(Jan.Feb,Mar.Apr,May.June,July,Aug,Sep,Oct,Nov,Dec)

(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后

的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。

(1)求得的二叉排序树如下图所示，在等概率情况下查找成功的平均查找长度为

ASJ=表(1X1+2X2+3X3+4X3+5X2+6XD=1|

▲注：中序遍历二又排序树,得到从小到大序列

根据字母的先后确定大小

①插入Jan：②F不不小于J,Feb成为Jan左子树：③M不小于J,Mar成为Jan右子

树；④Apr不不小于Jan,且Apr不不小于Feb,Apr成为Feb左子树；⑤May不小于Jan,

且May不小于Mar,May成为Mar右子树：⑦June不小于Jan,且June不不小于Mar,

June成为Mar左了树。剩余的略。

◎二叉排序树删除()

3种状况：

(1)*P为叶子节点，直接删除。

(2)*p只有一种孩子*child只需将*child和*p的双亲直接连接后,即可

删去*P。

(3)*p有两个孩子

用*P的直接前驱或直接后继替代*P，然后删除它的直接前驱或直接

后继。

◎平衡二叉树：树上任何节点的左右了•树深度差都不超过1

▲插入节点1〉后不平衡，找到离P近来的不平衡点根据二叉排序树的建立进行调

整。

序列：Jan,Feb,Mar,Apr,May,June,July,/lug,Sep,Oct,Nov,Dec

I

(jujD(Jdy2)

(i)变化后(1)

(1)插