2023年人武学院数据结构课后习题答案及期末综合练习

第十章内部排序

一、基本知识题答案

1.排序：将•组杂乱无序的数据按一定『'J规律顺次排列起来叫做排序。

内部排序：数据存储在内存中，并在内存中加以处理的排序措施叫内部扑序。

堆：堆是一种完全二叉树，它的每个结点对应于原始数据的一种元素，且规定假如i种结点有儿子结点，此结点数据必须

不小于或等于其儿子结点数据。

稳定排序：一种排序措施，若排序后具有相似关键字的记录仍维持本来的相对次序，则称之为稳定的，否则祢为不稳定的。

2.回答卜面问题

(1)5000个无序的数据，但愿用最迅速度挑选出其中前10个最大的元素，在迅速排序、堆排序、归并排序和基数排序

中采用哪种措施最佳？为何？

(2)大多数排序算法均有哪两个基本操作？答：(I)采用堆排序最佳。

由于以上几种算法中，迅速排序、归并排序和基数排序都是在排序结束后才能确定数据元素的所有次序，而无法懂得排

序过程中部分元素的有序性。堆排序则每次输出一种最大(或最小)的元素，然后对堆进行调整，保证堆顶的元素总是余下

元素中最大(或最小)的。根据题意，只要选用前10个最大的元素，故采用堆排序措施是合适的。

(2)两个基本操作：比较两个关键字的大小、变化指向记录H勺指针或移到记录自身。

3.3.已知序列｛17,25,55,43,3,32,78,67,91),请给出采用冒泡排序法对该序列作递增排序时每一趟的成果。

答：采用冒泡排序法排序时的各趟成果如下：

初始：17,25,55,43,3,32,78,67,91

第1趟:17,25,43,3,32,55,67.78,91

第2趟：17,25,3,32,43,55,67.78,91

第3趟：17,3,25,32,43,55,67.78,91

第4趟：3,17,25,32,43,55,67.78,91

第5趟：3,17,25,32,43,55,67,78,91

笫5趟无元素互换，排序结束。

4.已知序列{491,77,572,16,996,101,863,258,689,325},请分别给出采用迅速排序、堆排序和基数排序法对该

序列作速增排序时每一档的成果。

答：采用迅速排序法排序时的各超成果如下:

初始:491,77,572,16,996,101,863,258,689,325

第1趟：[325,77,258,16,101]491[863,996,689,572]

第2趟；[101,77,258,16]325,491[863.996,689,572]

第3趟：[16,77]101[258]325,491[863,996,689,572]

第4趟：16(77]101(258)325,491[863,996,689,572]

笫5趟：16,77,101(258]325,491[863,996,689,572]

第6趟：16,77,10b258,325,491[863,996,689,572]

第7趟:16,77,101,258,325,4911572,6891863[996]

第S趟:16,77,101,258,325,491,572[689]863[996]

第9趟:16,77,I0L258,325,491,572,689,8631996]

第10趟：16,77,101,258,325,491,572,689,863,996

采用堆排序法排序时各趟的成果如下图所示:

(a)初始堆(b)建堆

(c)互换996和77,输出996(d)筛选调整

采用基数排序法排序时各趟的成果如下:

初始：491,77,572,16,996,101,863,258,689,325

第1趟(按个位排序)：491,101,572,863,352,16,996,77,258,689

第2趟(按十位排序):101,16,352,258,863,572,77,689,491,996

第3趟(按百位排序)：16,77,101,258,352,491,572,689,863,996

5.已知序列［86,91,138,62,41,S1,18,32},请给出采用插入排序法对该序列作递增排序时，每一趟的成果。

答：采用插入排序法排序时各趟的成果如下:

初始:(86),94,138,62,41,54,18,32

第1趟:(86,94),138,62,41,54,18,32

第2趟:(86,94,138),62,41,54,18,32

第3趟:(62,86,94,138),41,54,18,32

第4趟:(41,62,86,94,138),54,18,32

第5趟:(41,54,62,86,94,138),18,32

第6趟:(18,41,54,62,86,94,138),32

第7.趟：(18,32,41,54,62,86,94,138)

6.已知序列{27,35,11,9,18,30,3,23,35,20},请给出采用归并排序法对该序列作递增排序时的每一趟的成果。

答：采用归并排序法排序时各趟的成果如卜.：

初始:27,35,11,9,18,30,3,23,35,20

第1趟：[27,35][9,11][18,30][3,23][20,35J

第2趟：[9,11,27,35][3,18,23,30][20,35]

第3趟：[9,11,27,35][3,18,20,23,30,35]

第4趟:[3,9,1b18,20,23,27,30,35,35]

二、算法设计题答案

1.二、算法设计题

1.一种线性表中H勺元素为所有为正或者负整数，试设计一算法，在尽量少的时间内重排该表，将正、负整数分开，使线性

表中所有负整数在正整数前面。

解：本题的算法思想是：设置两个变盘分别指向表的首尾，它们分别向中间移动，指向表首的

假如碰到正整数，指向表尾的假如碰到负整数则互相互换，然后继续移动直至两者相遇。实现本

题功能的算法如下：

voidpart(intarray!n)

{

inti.j;

i=l；

j=n；

wh.le(i<j)

while(i<j&&array[iJ<0)

i++；

while(i<j&&array[j]>=0)

j-；

ilXKj)

(arraylO]=arrayli];

arrayli]=arniy|j];

array(j]=airay|O];

I

}

)

2.设计一种用单链表作存储构造的直接插入排序算法。

解：实现本题功能的算法如下：

voidinserisort(nodc*hcad)

(

node*p,*q.*pre;

pre=head;

p=head->next;/*p指向待插入的元素*/

while(p!=NULL)

q=head;

if(p->key<q->key)/*插到表首*/

{pre->next=p->next;

p->next=hcad;

hcad=p;

)

else

(

while(q->next!=p&&q->next->key<p->key)

q-q>next;

if(q->next==p)

(

pre=p;

p=p->ncxt:

)

else

{pre->next=p->next;

p->next=q->next;

q->next=p;

p=pre->next;

)

}

3.试设计一种算法实现双向冒泡排序。(双向冒泡排序就是在排序的过程中交替变化扫描方向。)

解：实现本题功能的算法如下：

voiddbubblcson(sqlisir,inin)

(

inti.j.tlag;

flag=1;

i=l；

while(flag!=O)

(

flag=O;

for(j=ij<n-i:j++)

(

if(rUl>rU+U)

(

flag=l;

r|O]=r[j];

rUl=rU+U；

rU+ll=r[Ol；

}

for(j=n-iy>i;j-)

(

{nag=l;

rlO]=r|j];

rljMj-l]；

rU-U=r|OJ;

I

)

i++；

)

)

4.设一种一维数组A[n]中存储了n个互不相似的整数,且这些整数时值都在0到n-1之间,即A中存储了从0到n-1这n个

整数。试编写一算法将A排序，成果有存在数组B[n]中，规定算法的时间复杂性为O(n)。

解：实现本题功能的算法如下：

voidsort(intA(n].intBln])

(

inti;

for(i=0:i<n;i++)

B[A[i]]=A[i];

}

第一章

一、基础知识题

1.(1)皆找：杳找又称为查询或检索，是在一批记录中根据某个域的指定域值，找出对应H勺记录H勺操作。

(2)树型查找：将原始数据表达成二又排序树，树I为每个结点刈成一种记录，运用此二又排序树进行类似于二分直找思想

的数据查找，这种查找措施称为树型查找。

(3)平衡因子：二叉树中每一结点的左子树高度减右子树高度为该结点欧平衡因F.

(4)散列函数：根据关键字求存储地址的函数称为散列函数。

(5)两个不一样I内关键字，其散列函数值相似，因而被映射到同一种表位置上的现象称为冲突。

2.设有序表为{a,b,c,d,e,f,g},请分别而出对给定值f,g和h进行拆半查找的过程。

答：查找f的过程如下：1abedefgJ

ttt

lowmidhigh

abcd[efg]

ttt

查找成功，找到k=f值lowmidhigh

查找g的过程如下：

Iabcdefg]

IIf

lowmidhigh

abcd[efg]

Iti

lowmidhigh

abcdef[g]

nt

lowhigh

查找成功，找到k个值

查找h的过程如下:

[abcdefg]

tt|

lowmidhigh

abcd[cfg]

Iti

lowmidhigh

abcdef[g]

tn

lowhigh

3.试述次序查找法、二分查找法和分块查找法对被查找表中元素的规定，每种查找法对长度为nl内表的等概率查找长度是

多少

答：次序查找法：表中元案可以任意存存。青找成功的平均直找长度为(什1)/2。

二分查找法：表中元素必须以关键字的值递增或递减地寄存且只能以次序表寄存。查找成功的平均查找长度

为og2(n+l)-l。

分块查找法：表中每块内的元素可以任意寄存，但块与块之间必须按关键字的大小递增或递减地寄存，即前

一块内所有元素的关犍字不能大(或小)于后一块内任意一种元素的关键字.若用次序查找确定所在块，平均查找长度为

l/2：n/s+s)+l；若用：分查找确定所在块，平均查找长度为log2(n/s+l)+s/2,

4.设散列表长m=14,哈希函数为H(k)=kmod11,表中洪有8个元素{15,27,50.73,0},试画出采用:次探测法

处理冲突的散列表。

答：采用二次探测法处理冲突的散列表如下：

012345678910II1213

6037152750734910

5.线性表的关键字集合为{113,12,180,138,92,67,94,134,252,6,70,323,60},共有13个元素,已知散列函数为：H(k)=kmod13,

采用链接表处理冲突，试设计这种链表构造。

答：由题意，可得:

H(I13)=113%13=9

11(12)=12%13=12

H(I8O)=180%13=11

H(138)=138%13=8

H(92)=92%13=1

H(67)=67%13=2

H(94)=94%13=3

H(I34)=134%13=4

H(252)-252%13-5

H(6)=6%13=6

11(70)=70%13=5

H(323)=323%13=11

0-I56|4~"[49"pn

1|1hl

265A

3A

4A

5

6

7A

8A

9A

6.设关键字集合为{27,49,79,5,37,1,56,65,83},散列函数为：H(k)=kmod7,散列表长度m=10,起始地址为0,分别用线

性探测和链接表法来处理冲突。试画出对应的散列表。

答：线性探测法的散列表如卜图所示：

0123456789

4917937565276583

链接表法H勺散列表如F图所示：

二、算法设计题

1.从小到大排列的，试写出对此链表的查找算法，并阐明与否可以采用折半查找。解：实现本题功能的算法如下，假如查找

成功，则返回指向关键字为x的结点的指针，否则返回NULL。

node*sqsearch(node*x)

(

node*p=head;

while(p!=NULL)

if(x>p->key)

p=p->link;

elseif(x==p->kcy)

returnp;

else

p=NULL;

returnp;

)

)

虽然链表中的结点是按递增次序排列的，不过其存储构造为单链表，查找结点时只能从头指针开始逐渐进行搜索，因此不能

用折半查找。

2.假如线性表中各结点查找概率不等，则可以使用下面的方略提高次序表内查找效率：假如找到指定的结点，则将该结点和

其前趋(若存在)结点互换，使得常常被查找『'J结点尽量位于表的前端。试对线性表的次序存储构造和链式存储构造写出实

现上述方略的次序查找算法(注意查找时必须从表头开始向后扫描)。

解：采用次序存储构造的算法如下，；殳记录存储在线性表口勺In单元中。假如查找成功，返回关键字为k的记录在线性表

中的位置，假如失败则返回0。

intseqsearch(sqlistrjntn,intk)

(

intij:

i=l；

while((r[i].key!=k)&&(i<=n))

i++；

if(i<=n)

r|0]=r|i];

r[i]=r(i-ll;

r[i-l]=r[i]；

1-;

return(i);

}

elserelurn(O);

)

采用链式存储构造『'J算法如下。假如查找成功，则返回指向关键字为k的结点的指针，否则返回NULL。

rode*seqsearch(no<le*head,intk)

{

if(head>key-k)

return(head);

else

(

node*p.*q:

intx;

p=head;

q=head->link;

while(q!=NULL&&q->key!=k)

{

p=q:

q=q->)ink;

if(q!=NULL)

x=p->key;

p->key=q->key;

q->kcy=x;

q=p;

)

return(q);

I

)

3.试设计一种在用开放地址法处理冲突的散列表上删除一种指定结点的算法。

解：本题的算法思想是：首先计算要删除H勺关健字为k的记录所在的位置，将其置为空(即删除)，然后运压线性探测法查

找与否有与k发生冲突而存储到下一地址H勺记录，假如有则将记录移到本来k所在的位置.，直至表中没有与k冲突H勺记录为

止。实现本题功能的算法如下：

voidclelcte(sqlis(r,intn,inlk)

(

inth.hO.hl;

h=k%n:

while(r|h|.key!=k)

h=(h+l)%n:

r|h]=NULL;

hO=h;

hl=(h+l)%n;

whilc(hl!=h)

(while(r[hI].key%n!=h)

hl=(hl+l)%n;

r[hO]=r(hlJ;

r[hl]=NULL;

hO=hl;

hl-(hl+l)%n;

)

)

4.设给定时散列表存储空间为每个单元可寄存一种记录，H⑴(IWiWm)的初始值为零，选用散列函数为H(R.kcy),

其中key为记录R的关健字，处理冲突措施为线性探测法，编写一种函数将某记录R填入到散列表H

解：本题的算法思想：先计算地址H(R.key),假如没有冲突，则直接填入；否则运用线性探测法求出下一地址，直到找到一

种为零的地址，然后填入。实现本题功能的函数如下：

voidinsert(recordH,intm.recordR)

{

inti;

i=H(R.key);

if(H[i]==NULL)

H[i]=R;

else

while(H[i]!=NULL)

(

i=(i+l)%(m+l);

)

H[i]=R;

1

)

第七章

一、基本知识题

I.图H勺逻辑构造特点是什么？什么是元向图和有向图？什么是子图？什么是网络？

答：图是比树更为免杂H勺一种非线性数据构造，在图构造中，每个结点都可以和其他任何结点相连接。

无向图：对于一种图G,若边集合E(G)为无向边的集合，则称该图为无向图。

有向图：对于一种图G,若边集合E(G)为有向边的集合，则称该图为有向图。

子图:设有两个图G=(V,E)和G'=(V',E'),若V(G')是V(G)『、J子集，且E(G')是E(G)『、J子集，则称G'是G的子

图(Subgraph)。

网络：有些图，对应每条边有•对应的数值，这个数值叫做该边的权。边上带权的图称为带权图，也称为网络。

2.什么是顶点的度？什么是途径？什么是连通图和非连通图？什么是非连通图的连通分量？

答：顶点的度：图中与每个顶点相连的边数，叫该顶点的度。

在一种图中，若从某顶点Vp出发，沿某些边通过顶点VLV2,…,Vm抵达，Vq,则称顶点序列(Vp,V1,V2,…,Vm,Vq)为

从Vp到Vq的途径。

在无向图中，假如从顶点Vi到顶点Vj之间有途径，则称这两个顶点是连通的。假如图中任意一对顶点都是连通的，则

称比图是连通图。

非连通图的连通分量：非连通图的每一种连通的部分叫连通分量。|2।

11I-RI3I-H5hl

3.给出图6.25所示的无向图G的邻接矩阵和邻接表两种存储构造。

HI-H[T'E~|

答：图G所对应的邻接矩阵刘下:图G所对应的邻接表如下:

0101Oil11I5|AI

101012[FTHTKI

A=010103

101014

ioi0J5

0

4.假设图的顶点是A、B……请根据下面的邻接矩阵画出对应的无向图或有向图。

■（）11r01100-

101100010

10001

110110000

111001010

⑧

答：深度优先搜索得到H勺顶点访问序列：0、1、3、7、8、4、9、5、6、2：

广度优先搜索得到的顶点访问序列：0、1、2、3、4、5、6、7、

6.应用prim算法求图6.27所示带权连通图的最小生成树。

答：该图的最小生成树如下：

7.写出图6.28所示有向图的拓朴排序序列

答：该有向图的拓朴排序序列为：3、I、4、5、2、6°

二、尊法设计题图28

二、算法设计题答案

I.如图6.29所示图G,试给出其对应的邻接表，并写出深度优先算法。解：该图对应的邻接表如下:

深度优先算法：

voiddfsgraph(adjlistadj,intn)

/*深度优先遍历整个图*/

|

inti;

for(i=l:i<=n;i++)

visited[i]=0;

for(i=l;i<=n;i++)

if(!visited[i])

dfs(adj,i);

voiddfs(adjlistadjJntv)

产以v为出发点，对图进行dfs遍历*/

structedgenode*p;

visi(c<l(v]=l;

printf("%d",v);

p=adj[vl-link:

while(p!=NULL)

(if(visited[p-*adjveK]==O)

dfs(adjlisl,p-*adjvex);

p=p-*next;

}

)

2.如图6.29所示图G,试给出其对应的邻接矩阵，并写出广度优先算法。

解：该图对应的邻接矩阵如下:

123456789

广度优先算法：

■()1100000Oil

1001100002

voidbfsgraph(intadjarniyln||n|.intn)

1000011003

0I00000104

八广度优先遍历整个图*/

A=0100000105

0010000016

(

00i0000017

0001100018

inti;()J9

00000111

for(i=0;i<n;i++)

visited[il=O;

for(i=0;i<n;i++)图29

if(!visited[i])

bfs(adjarray.i);

voidbfs(intadjarray[][],intv)

产以v为出发点，对图进行bfs遍历*/

inti.j;

queueq;

printf("%d",v);

visited[v]=1;

enqueuc(&q.v):

whilc(!qucucenny(&q))

i=dequeue(&q);

for(j=0;j<n;j++)

if(adjarray[i]|j]==1&&!visited[j])

printf("%d".j);

visited[j]=l;

enqueue(&q.j);

3.编写一种函数通过与顾客交互建立一种勺向图H勺邻接表。

解：实现本题功能的算法如下：

voidcreategraph(adjlistg)

{

inte.i.s.d.n;

structedgenode*p;

prinif("请输入结点数(n)和边数(e):\n");

scanf("%d,%d",&n,&e);

fbr(i=l:i<=n:i++)

(

printf("\n请输入第％d个顶点信息：",i);

scanf("%c",&g[i].data);

gli].link=NULL;

)

fbr(i=l;i<=e:i++)

{prinif("\n请输入第％(1条边起点序号，终点序号：",i);

scanf("%d,%d",&s,&d);

p=(structedgenode*)malloc(sizeof(edgenode)):

p-*adjvex=d;

p-*next=g[s].link;

g(s].link=p;

}

)

4.编写一种无向图Rj邻接矩阵转换成邻接表的算法。

解：本题的算法思想是：逐扫描邻接矩阵的各个元素，如第i行第j列的元素为I,则时应的邻接表的第i个单链表上增

长一种j结点。实现本题功能的算法如下；

voidtransfbrin(intadjarray[n][n],adjlistadj)

(

inti.j;

edgenode*p:

for(i=0;i<n;i++)

(

adj[ij.data=i;

adj[i].link=NULL;

)

for(i=0;i<n;i++)

fbr(j=O;j<n:j++)

if(adjarray(ij[j)==l)

p=(edgeno<le*；malloc(sizeof(edgenode));

p-*adjvex=j;

p-*ncxt=adjlij.link;

adj[i].link=p;

)

)

I

5.己知•种有n个顶点的有向图的邻接表，设计算法分别实现

1)求出图中每个顶点的山度。

2)求出图中每个顶点的入度。

3)求出图中出度最大H勺一种顶点，输出其顶点序号。

4)计算图中出度为0的顶点个数。

解：(1)本题H勺算法思想是：计辨出邻接表中第i个单链表的结点数，即为i顶点的出度。求顶点的出度数的克法如卜.:

intouldegrec(adjlistadj,intv)

{intdegree=O;

edgenode*p:

p=adjlv].link;

while(p!=NULL)

(degree++;

p=p->next;

}

returndegree;

voidprintout(adjlis(adj,intn)

(

inii,dcgrcc;

printf("Theoutdegreesare:\n");

for(i=0;i<n;i++)

(

degree-outdegree(adj.i);

printf("(%d,%d)",i,degree);

}

)

(2)本题的算法思想是：计算出整个邻接表中所具有H勺结点为iH勺结点数，这就是i顶点的入度。求顶点H勺入度数的算法:

intindegrec(adjlisladj,intn,intv)

{

inti,j.degree;

edgenode*p;

for(i=0;i<n;i++)

(

p=adj[i].link:

while(p!=NULL)

if(p->adjvex==v)

dcgrcc++;

p=p->ncxt;

}

)

returndegree;

I

voidprintin(adjlistn)

(

inti.degree:

printf("Theindegreesare:\n");

fbr(i=0:i<n:i++)

{

dcgree=indcgree(adj,n,i);

printf("(%d.%d)",i.degree);

I

I

(3)求最大出度的算法：

voidmaxoutdegree(adjIistn)

intmaxdegree=O.maxv=O.degree,i;

for(i=0;i<n;i++)

(

degrcc=ouidegrcc(adj,i);

if(dcgrce>maxdcgrcc)

(

niaxdegree=degree;

maxv=i;

I

}

printfC'maxoutdegree=%d.

maxvertex=%d",maxdegree,maxv);

)

(4)求出度数为0H勺顶点数的算法：intoutzero(adjlistadj,intn)

{

intnum=O,i;

fbr(i=O;i<n;i++)

(

if(outdegree(adj.i)==0)

num++;

)

returnnum:

笫六章

一、基础知识题

i.就如图5.21所示H勺树回答下面问题:

I）哪个是根结点？

2）哪些是叶子结点？

3）哪个是E的父结点？

4）哪些是E的子孙结点？

5）哪些是E的兄弟结点？哪些是C的兄弟结点？

6）结点B和结点I的层数分别是多少？

7）树H勺深度是多少？

8）以结点G为根的子树的深度是多少？

9）树H勺度是多少？

答：1）A是根结点

2）D、H、I、J、F、G是叶子结点

3）B是E『、J父结点

4）H、I、J是E的子孙结点

5）D是EH勺兄弟结点，B是CI向兄弟结点

6）BI内层数是2,II内层数是4

7）树的深度是4

8）以结点G为根的子树的深度是1

9）树的度是3

2.分别画出含3个结点口勺树与二叉树口勺所有不一样形者

3.高度为完全二叉树至少有多少个结点？最多有多少个结点？

答：高度为hH勺完全二叉树至少有个结点，最多有个结点。

4,采用次序存储措施和链式存储措施分别画出图5.22所示二叉树的存储构造。

答：该二又树口勺次序存储:

0123455789101112131415

9123456789

该二叉树的链式存储:

5,分别写出图5.22所示二叉树的前序、中序和后序遍历序歹上

图22

答：先序遍J力序列：1、2、4、7、3、5、8、6、9

中序遍历序列：7、4、2、1、8、5、3、6、9

后序遍历序列：7、4、2、8、5、9、6、3、1

6.若二叉树中各结点值均不相似。

1)已知一种二叉树的中序和后序遍历序列分别为GDHBAECIF和GHDBEIFCA,请画出此二叉树。

答:

7.一种二叉树如图5.23所示，分别写出其前序、中序、后序的遍历序列。

答：先序遍历序列：A、B、D、E、F、C、G

中序遍历序列：D、F、E、B、A、G、C

后序遍历序列：F、E、D、B、G、C、A

8.输入一种正整数序列｛55,34,18,88,119,11,76,9,97,99,46),试构造一种二叉排序树。

9.有一份电文中共使用5个字符:a、b、c、d、e,它们的出现频率依次

为5、2、1、6、40试画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。

9

99

第8题各字符对应的哈夫曼编码如下:

a:10.b:001.c:000,d:H.e:01

二、算法设计题答案

I.一种二叉树以链式构造存储，分别给出求二叉树结点总数和叶子结点总数的算法。

解：求二叉树结点总数的算法如下：

in:CounlNode(btreenum)/*num初值为0”

{if(t!=NULL)

num=CountLeaf(t->right.nuni);

num++;)

num=CountNode(t->left,num);returnnum:

num=CountNode(t->right,nuin);}

)2.2.一和二叉树以链式构造存储，写出在二叉树中查找值为x

returnnum:H勺结点的算法。

)解：本题可以用先序、中序和后序遍历中的任意一种遍历，只

求二叉树叶子结点总数的算法如下：要将遍妨算法中的访问根结点改为判断其值J否等于Xo下面

intCountLeaf(btree*num)/*num初值为0*/是用中序遍历求解的算法，函数返回值为x时结点的地址，若

{if(t!=NULL)没有找到则返回空。

Ibtree*search(btree*x.btreep)

if(t->left==NULL&&t->right==NULL)/*p的初值为NULL*/

num++;(

num=CountLeaf(t->left.num);if(t!=NULL)

解：按中序序列遍历二叉排序树即按递增次序遍历，因此递增

p=search(t->left,x,p)；打印二叉排序树各元素值的函数如下：

if(t->data==x)voidinorder(btree*t)

p=t;/*找到x的地址放在p中*/(

p=search((->righl,x,p);if(t!=NULL)

)(

returnp;inorder(t->lefl);

}printf("%d",t->data);

3.设计一种算法将一种以链式存储构造的二叉树，按次序方inorder(t->right);

式存储到一维数组中。)

解：这是一种递归算法，如下：}

voidcreate(btreetree[],inti)5.已知一种中序线索二叉树，试编写中序遍历的非递归算法。

(解：在中序线索二叉树中进行非递归中序遍历，只要从头结点

if(l!=NULL)出发，反复找到结点n勺后继，直至结束即可.在中序线索二叉

{树中求结点后继的算法如下：

tree[i]=t-xiata;tbtree*succ(tbtree*p)

create(t->left,tree.2*i);(

create(t->right.tree.2*i-»-1);