数据结构(C语言描述)马秋菊源代码与习题答案

1、习题配套第一章2C、A、B、B、A、A、D3D=A,B,C,E,F,G,H,I,J;R=<A,B>,<A,C>,<A,E>,<B,F>,<B,G>,<E,H>,<E,I>,<E,J>,<H,I>,<I,J>ABCEFGHI题1-3图 J4顺序、链式、索引、哈希。*5解：100n2>2nn至少要多大6.(n)、(n)、(n)、()、(5)当n>m，(n),当m>n，(m)7n!2100>lgn>n1/2>n3/2>(3/2)n>2

2、n>nlgn>nn第二章1×、×、2AAD4顺序表void Delete_SeqListx(SeqList *L,ElemType x)/*删除表中值为x元素*/inti,j;for(i=1;i<=L->length;i+)if(L->elemi=x)for(j=i;j<=L->length-1;j+)L->elemj=L->elemj+1;L->length-;/*向上移动*/O(n2)链表void del_link(LinkList H，int x)/*删除数据域为x的结点*/LNode *p，*q;p=H;q

3、=H->next;while(q!=NULL)if(q->data=x)p->next=q->next;free(q);q=p->next;elsep=q;q=q->next;O(n)5int Delete_SeqListx(SeqList *L,int i,int k)/*删除表中删除自第i个结点开始的k个结点*/intj;if(i<1|k<0|i+k-1>L->length)/*检查空表及删除位置的合法性*/printf(不存在第i个元素);return ERROR;for(j=i;j<=L->length-k;j+)

4、L->elemj=L->elemj+k; /*向上移动*/L->length-=k;Return OK;/*删除成功*/O(n)6void Delete_SeqListx(SeqList *L,ElemType x)/*将表中值为x元素换成y*/inti,j;for(i=1;i<=L->length;i+)if(L->elem=x)L->elemi=y;/* */O(n)7写一算法在循环单链表上实现线性表的CList_length(L)运算。int link_length(LinkList H)LNode *p;int i=0;p=H;while(p-

5、>next!=H)i+;p=p->next;return i;O(n)8在用头指针表示的单循环链表中，查找开始结点a1的时间是O(1)，然而要查找终端结点则需从头指针开始遍历整个链表，其时间是O(n)。但在很多实际问题中，表的操作常常是在表的首、尾位置上进行，如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是rear->next->next和rear，显然，查找时间都是O(1)。9.int Insert_LinkListab(LinkList H, ElemType a,ElemType b)/*在单链表中值为a的结点

6、前插入一个值为b的结点*/LNode*q=H,*s;*p=H->next;while(p!=NULL&&p->data!=a) /*q->next&&q->next->data!=a*/q=p;p=p->next;/*查找a结点*/s=(LinkList)malloc(sizeof(LNode);/*申请、填装结点*/s->data=b;s->next=q->next;/*新结点插入在第i-1个结点的后面*/q->next=s；return OK;/*Insert_LinkListab*/10顺序表vo

7、id Reverse_Sq(SqList *L)/*顺序表的就地逆置*/for(i=1，j=L.len;i<j;i+)t=L.elemi;L.elemi=L.elemL.len-i+1;L.elemL.len-i+1=t;/*Reverse_Sq*/单链表void Reverse_L(LinkList *H)/*为简化算法，假设表长大于2*/p=H->next;q=p->next;s=q->next;p->next=NULL;while(s->next)q->next=p;p=q;q=s;s=s->next;/*把H的元素逐个插入新表表头*/q-

8、>next=p;s->next=q;H->next=s;/*Reverse_L*/分析：本算法的思想是，逐个地把L的当前元素q插入新的链表头部，p为新表表头。11void merge1(LinkList &A,LinkList &B,LinkList &C)/*把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间*/p=A->next;q=B->next;C=A;while(p&&q)s=p->next;p->next=q;/*将B的元素插入*/if(s)t=q->next;q->next=s

9、;/*如A非空,将A的元素插入*/p=s;q=t;/*while*/*merge1*/12Status Delete_Pre(CiLNode s)/*删除单循环链表中结点p的直接前驱*/q=p;while(q->next->next!=p)q=q->next;/*找到p的前驱的前驱*/s=q->next;q->next=p;free(s);return OK;/*Delete_Pre*/13Status Insert_SqList(SeqList &L，int x)if(L->length+1>m-1)return ERROR;L->le

10、ngth+;i=L->length;while(L->elemi>x&&i>0;)L->elemi+1=L->elemi;i-;L->elemi+1=x;return OK;/*Insert_SqList14intInsert_Linkx(LinkList H,ElemType x)/*在值递增单链表中插入一个值为x的结点，仍递增*/LNode*q=H,*s;*p=H->next;while(p!=NULL&&p->data<x)/*q->next&&q->next->

11、data<x*/q=p;p=p->next;/*查找a结点*/s=(LinkList)malloc(sizeof(LNode);/*申请、填装结点*/s->data=x;s->next=q->next;/*新结点插入*/q->next=s；return OK;/*Insert_Linkx*/15源程序代码：（在TubroC2.0测试通过）#include<stdlib.h>#include<alloc.h>structnodeintnumber;/*人的序号*/intcipher;/*密码*/structnode*next;/*指向下

12、一个节点的指针*/;structnode*CreatList(intnum)/*建立循环链表*/inti;structnode*ptr1,*head;if(ptr1=(structnode*)malloc(sizeof(structnode)=NULL)perror("malloc");returnptr1;head=ptr1;ptr1->next=head;for(i=1;i<num;i+)if(ptr1->next=(structnode*)malloc(sizeof(structnode)=NULL)perror("malloc"

13、);ptr1->next=head;returnhead;ptr1=ptr1->next;ptr1->next=head;returnhead;main()inti,n=30,m;/*人数n为30个*/structnode*head,*ptr;randomize();head=CreatList(n);for(i=1;i<=30;i+)head->number=i;head->cipher=rand();head=head->next;m=rand();/*m取随机数*/i=0;/*因为我没办法删除head指向的节点，只会删除head的下一节点，所以只

14、能从0数起。*/while(head->next!=head)/*当剩下最后一个人时，退出循环*/if(i=m)ptr=head->next;/*ptr记录数到m的那个人的位置*/printf("number:%dn",ptr->number);printf("cipher:%dn",ptr->cipher);m=ptr->cipher;/*让m等于数到m的人的密码*/head->next=ptr->next;/*让ptr从链表中脱节，将前后两个节点连接起来*/head=hea/d->next;/*head

15、移向后一个节点*/free(ptr);/*释放ptr指向的内存*/i=0;/*将i重新置为0，从0再开始数*/elsehead=head->next;i+;printf("number:%dn",head->number);printf("cipher:%dn",head->cipher);free(head);/*让最后一个人也出列*/16void SqList_Intersect(SqList A,SqList B,SqList &C)/*求元素递增排列的线性表A和B的元素的交集并存入C中*/i=1;j=1;k=0;whil

16、e(A.elemi&&B.elemj)if(A.elemi<B.elemj)i+;if(A.elemi>B.elemj)j+;if(A.elemi=B.elemj)C.elem+k=A.elemi;/当发现了一个在A,B中都存在的元素,/就添加到C中i+;j+;/*while*/*SqList_Intersect*/17Status DuLNode_Pre(DuLinkList*H)/*完成双向循环链表结点的pre域*/p=H;while(q->next!=H)p->next->pre=p;p=p->next;return OK;/*DuLN

17、ode_Pre*/第三章 栈与队列1假定有编号A、B、C的3辆列车顺序开进一个栈式结构的站台，请写出每一种开出站台的列车编号顺序(注：每一列车开出栈开出站台后，不允许再进栈)。2指出下述程序段的功能是什么？ void Demo1(SeqStack *S) int i; arra16;n=16；initStack(&S);for(i=0,i<n; i+) push(S,arrai); while(!StackEmpty(S) arrai =pop(S);3写出带表头链栈取栈顶元素和置栈空的算法。4假设一个算术表达式中包含圆括号、方括号和花括号，编写一个判别表达式中括号是否配对的算法

18、。5写出计算表达式5+3*（4/6-7）时操作数和算符栈的变化情况。6对于给定的十进制正整数，输出对应的八进制正整数。(1)写出递归算法。(2)写出非递归算法。7已知n为大于等于零的整数，试写出计算下列递归函数f(n)的递归和非递归算法。1 n=0 n*f(n/2) n0 f(n)= 8回文是指正读和反读均相同的字符序列，如”abba”和”abdba”均是回文，而”ashgash”不是回文。试写一个算法判断读入的一个以为结束符的字符序列是否为回文。(提示：将一半字符入栈)。9一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。设计初始化InitStack(S,i)、入

19、栈push(S,i,x)和出栈pop(S,i)等算法，其中i为0或1，用以指示栈号。10对于一个具有m个单元的循环队列，写出求队列中元素个数的公式。11循环队列的优点是什么？如何判别它的空和满？12假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素位置(注意不设头指针)，试编写相应的置空队、判队空、入队和出队等算法。13假设用一个数组QM来表示队列，该队列只设一个队头指针front，不设队尾指针，用计数器count来记录队列中元素的个数。试编写出相应的置空队列、入队列和出队列的算法。 14设长度为n的链队列用单循环链表表示，若只设头指针，则入队出队操作的时间复杂度是多少？若只设尾指

20、针呢？*15写一个算法，借助于栈将一个单链表置逆。1cba、acb、abc、bac、bca2将arra16数据元素倒置3写出带表头链栈取栈顶元素和置栈空的算法。typedef stack StackNode *top; LinkStack ;置空栈void Init_LS（LinkStack *s） StackNode *p=(StackNode*)malloc（sizeof（StackNode）;p->next=NULL;s=( LinkStack *)malloc（sizeof（LinkStack）;s->top= p; 判栈空int Empty_LS（LinkStack *s

21、 ） return s->top->next=NULL; 入栈 LinkStack *Push_LS（LinkStack *s , ElemType x） StackNode *p=(StackNode*)malloc（sizeof（StackNode）; p->data=x; p->next=s->top->next; /* 将元素x插入链栈顶 */ s->top->next =p ; return s; 出栈int Pop_LS(LinkStack *s , ElemType *y) StackNode *p; if （Empty_LS（s）

22、printf ("Stack Underflow.") ; /* 下溢 */ return OVERFLOW; else *y=s->top->next->data ; = s->top->next ; s->top->next=p->next ; free (p); return OK ; 取栈顶元素int GetTop(LinkStack *s,ElemType *y)if(Empty_LS(s )printf("Stack underflow.");/*下溢*/return OVERFLOW;else

23、*y= s->top->next->data;return OK;4Status AllBrackets_Test(char str)/*判别表达式中三种括号是否匹配*/InitStack(s);for(p=str;*p;p+)if(*p='('|*p=''|*p=''push(s,*p);else if(*p=')'|*p=''|*p='')if(StackEmpty(s)return ERROR;pop(s,c);if(*p=')'&&c!=&#

24、39;(')return ERROR;if(*p=')'&&c!=''return ERROR;if(*p=')'&&c!=''return ERROR;/*必须与当前栈顶括号匹配*/*for*/if(!StackEmpty(s)return ERROR;return OK;/*AllBrackets_Test*/或int PairBracket(char *S)/*检查表达式中括号是否配对*/int i;SeqStack T;/*定义一个栈*/InitStack(&T);for(i

25、=0;i<strlen(S);i+)if(Si='(')Push(&T，Si);/*遇'('时进栈*/if(Si=')')Pop(&T);/*遇')'时出栈*/return !EmptyStack(&T);/*由栈空否返回正确配对与否*/5写出计算表达式5+3*（3/6-7）时操作数和算符栈的变化情况。 表达式5+3*（4/6-7）的求值过程 步骤运算符栈OPTR对象栈OPND读字符主要操作1#55+3*（3/6-7）#5入栈OPND2# +5+3*（3/6-7）#+入栈OPTR3# +5，33*（3

26、/6-7）#3入栈OPND4# + *5，3*（3/6-7）#*入栈OPTR5# + * (5，3（3/6-7）#( 入栈OPTR6# + * (5，3，34/6-7）#3入栈OPND7# +* ( /5，3，3/6-7）#/入栈OPTR8# + * ( /5，3，3，66-7）#6入栈OPND9# + * (5，3，0.5-7）#3，6出栈OPND，/出栈OPTR求4/6，结果0.5入栈OPND10# +* (-5，3，0.5-7）#-入栈OPTR11# +* (-5，3，0.5，77）#7入栈OPND12# + * (5，3，-6.5）#0.5，7出栈OPND，-出栈OPTR求0.5-7，

27、结果-6.5入栈OPND13# + *5，3，-6.5#( 出栈14# +5，-19.5#3，-6.5出栈OPND，*出栈OPTR求3*-6.5，结果-19.5入栈OPND15#-14.5#5，-19.5出栈OPND，*出栈OPTR,求5+-19.5，结果-14.5入栈OPND16#-14.5#RERTURN(-14.5) 6对于给定的十进制正整数，输出对应的八进制正整数。(1)写出递归算法。(2)写出非递归算法。(1)递归算法。void conversion1(int N, int R) if ( N<R)printf(“%d ”, N ) ;else conversion1(N/R,

28、R); printf ( “%d ”, N%R ) ;(2)非递归算法。void conversion2(int N, int R) SeqStack s ; int x ; Init_SeqStack(&s) ; while ( N ) Push_SeqStack ( &s ，N % R ) ; N=N/R ; while ( !Empty_SeqStack(& s ) ) Pop_SeqStack (&s , &x ) ; printf ( “ %d ”, x ) ; 7已知n为大于等于零的整数，试写出计算下列递归函数f(n)的递归和非递归算法。递归

29、算法long f1(int n) int f; if (n=0) f=1; else f=n*fact(n/2); return f; 非递归算法long f2 (int n) if (n=0) return 1; else InitStack(S);f=1; while (n>0) push(S,n); n=n-1 ; while (!EmptyStack(S) ) Pop(S,i); f=f*i; return (f) ; 8.void huiwen()Init_LS(s); printf("Please input a string:n"); for(i=0;(

30、i<20)&&(ai=getchar()!='n');+i); /*输入字符串*/ for(j=0;j<i/2;+j) /* 字符串的前一半入栈*/ Push_LS(s,aj); for(j=i-i/2;j<i;+j) /*出栈，与后一半字符串比较*/ Pop_LS(s,&ch); if(ch!=aj) break; if(!Empty_LS(s) printf("It is not a huiwen string!n" ); else printf("It is a huiwen string!n&quo

31、t; ); 9#defineM100elemtypestackM;inttop1=0，top2=m-1;intpush(ELEMTPx，inti)if(top1-top2=1)return(1);/*上溢处理*/elseif(i=1)stacktop1+=x;if(i=2)stacktop2-=x;return(0);intpop(ELEMTP*px，inti)if(i=1)if(top1=0)return(1);elsetop1-;*px=stacktop1;return(0);elseif(i=2)if(top2=M-1)return(1);elsetop2+;*px=stacktop2;

32、return(0);10对于一个具有m个单元的循环队列，写出求队列中元素个数的公式。 sq->rear-sq->front sq->rear>=sq->frontcount= m-(sq-> front-sq->rear) sq->rear<sq->front11循环队列的优点是什么？如何判别它的空和满？优点：防止假溢出；判别循环队列的空：return(sq->rear>=sq->front)；判别循环队列的满：return(sq->rear+1)%MAXSIZE=sq->front)12假设以带头结点的

33、循环链表表示队列，并且只设一个指针指向队尾元素位置(注意不设头指针)，试编写相应的置空队、判队空、入队和出队等算法。typedef struct qnode ElemType data; struct qnode *next; QCNode; /* 链式循环链队列结点的类型 */typedef struct QCNode *rear; LCQueue ; /* 只设一个指向队尾元素的指针 */（1）置空队算法：void Init_LCQueue(LCQueue *Lcq ) p=(QCnode*)malloc(sizeof(QCNode); /* 申请头结点 */ p->next=p;

34、Lcq->rear=p; （2）判队空算法：int Empty_LCQueue( LCQueue *Lcq) return Lcq->rear->next=Lcq->rear; /* 或Lq->rear=NULL; */ （3）入队算法：void In_LCQueue(LCQueue *Lcq , ElemType x) /*进队操作*/ LCQueue *p; p=(QCNode*)malloc(sizeof(QCNode); /* 申请新结点 */ p->data=x; p->next= Lcq->rear->next; Lcq->

35、;rear->next=p; Lcq->rear=p; /* In_LCQueue */（4）出队算法：int Out_LCQueue(LCQueue *Lq , ElemType *y) LCQueue p ; if (Empty_LCQueue(Lq) ) printf ("队空") ; return OVERFLOW ; /* 队空, 出队失败 */ else p=Lcq->rear->next->next; /* 队头第一个数据元素结点*/ Lcq->rear->next->next =p->next ; *y=

36、p->data; /* 队头元素放y中 */ free (p); return OK; 13假设用一个数组QM来表示队列，该队列只设一个队头指针front，不设队尾指针，用计数器count来记录队列中元素的个数。试编写出相应的置空队列、入队列和出队列的算法。typedef struct queuenode ElemType elemMAXSIZE; /* 队列中数据元素的存储空间 */ int front ,count; /* 队头指针、队中元素数量 */ CirQueue;/* 以上是结点类型的定义 */ void Init_Queue ( CirQueue *Q) /* 置空队 */

37、 Q->front=Q->count=0; int Empty_Queue( CirQueue *Q) /* 判队空 */ return (Q->count=0); int In_Queue (CirQueue *Q, ElemType x) /* 入队 */ if(Q->count=MAXSIZE) printf("队已满，不可以入队"); return OVERFLOW; Q->elem(sq->front+sq->count)%MAXSIZE=x; sq->count +; return OK; int Out_Queu

38、e( CirQueue *Q,ElemType *y) /* 出队 */ if(Empty_Queue(Q) printf("队已空，无元素可以出队"); return OVERFLOW); *y=sq->elemsq->front; /* 读出队头元素 */ sq->front=(sq->front+1)%MAXSIZE; sq->count-; return OK; int Front_Queue( CirQueue *Q, ElemType *y) /* 取队头元素 */ if(Empty_Queue(Q) printf("队空

39、，无元素可取"); return OVERFLOW); *y=sq->elemsq->front; /* 读出队头元素 */ return OK; 14设长度为n的链队列用单循环链表表示，若只设头指针，则入队出队操作的时间复杂度是多少？若只设尾指针呢？若只设头指针，则入队操作的时间复杂度是O(1)，出队操作的时间复杂度是O(n)；若只设尾指针，则入队操作的时间复杂度都是O(1)。*15写一个算法，借助于栈将一个单链表置逆。第4章 数组1请按行和按列优先顺序列出二维数组A3×4的所有元素在内存中的存储次序，开始结点为a00。a00 a10 a20 a01 a11

40、a21 a02 a12 a22 a03 a13 a232写出三维数组地址计算公式。设三维数组Am×n*p，先行，列，最后Z方向LOC（Aijk）= LOC（A00 0）+(i×m×n+j×m+k) ×L 3设有三对角矩阵A n×n，将其三条对角线上的元素逐行地存储到向量B03n-3中，使得Bk=aij，求：用i,j表示k的下标变换公式。Aij之间的对应关系为：k=2×i+j4二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M35的起始地址与M按列存

41、储时元素（ ）的起始地址相同。A. m24 B. M34 C. M35 D. M43M35 与M存储时元素M35 起始地址相同。5数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（1），若该数组按行存放时，元素A85的起始地址是（2），若该数组按列存放时，元素A85的起始地址是（）。 （1） A. 80 B. 100 C. 240 D. 270 （2） A.SA+141 B.SA+144 C.SA+222 D.SA+225（3） A.SA+141 B.SA+180 C.SA+222 D.SA+225（

42、1）C. （2） C. （3） A6对于二维数组Amn，其中m<=80，n<=80，先读入m，n，然后读入该数组的全部元素，对如下三种情况分别编写相应函数： (1) 求数组A边界元素之和。int sum( L ) int row,col,sum=0;for ( row=0;row<n;row+) sum= L0row;sum= sum+Lm-1row;/*列*/for (col = 0; col<n;col+) sum= Lcol0;sum= sum+ Lcolm-1; /*行*/ (2)求从A00开始的互不相邻的各元素之和；int sum2( L ) int row,

43、col,sum1=0,sum2=0;for ( row=0;row<n;row+,row+) for (col=0; col<n;col +, col +) sum1= sum1+Lrowcol; sum2= sum2+Lrow+1col+1; (3)当m=n时，分别求两条对角线的元素之和，否则打印m!=n的信息。int sum2( L ) int row,col,sum3=0, sum3=0;if(m!=n) printf ("m!=n !n");elsefor ( row=0;row<n;row+) sum3=sum3+Lrowrow; sum4=su

44、m4+Lrown-col; 7特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能？为什么？链式存储会失去随机存取的功能。8设稀疏矩阵A用十字链表表示，试编写下列算法：（1）已知i和j，查找Aii；QLNode * search(CrossList M, int i,int j) q=M->rheadi; while(q)&&(q->col<j) q=q->right; if(!q) printf(“not searched!”;return NULL;) p=M->cheadj; while(q)&&(q ->row<

45、;i) p=p->down; if(!p) printf(“not searched!”;return NULL;) return p;（2）已知数据元素的值x，查找 x 在A中的行、列号；QLNode * searchx(CrossList M,ElemType x) int i; /*mu,nu*/for (i=1;i< mu;i+) q=M->rheadi; if (q)&&(q->v<>x) q=q->right; else return q;9简述广义表和线性表的区别和联系。答：相同点：线性；不同点：数据元素分为原子和广义表。

46、10设广义表L=(),()，试问head(L),tail(L)，L的长度、深度各为多少？head(L)= ()tail(L)= ()L的长度为2。11求下列广义表运算的结果(1) head(a,b,c)= (a,b,c)；(2) tail(b,d,p,h) =()；(3) head(a,b),(c,d) =(a,b),(c,d)；(4) tail(a,b),(c,d) =()；(5)head(tail(a,b),(c,d) =()；(6) tail(head(a,b),(c,d) =()第6章 树树的形状acbfgdeljkimmh1.根据题意画出树的形状为右图：a是根结点，mndfjkl是叶

47、结点；c是g的双亲；c，a是g的祖先；j，k是g的孩子；imn是e的子孙；d是e的兄弟；g，h是f的兄弟；b的层次是2；n的层次是5；树的深度是5；以c为根的子树深度是3；树的度数是3。2三个结点的二叉树如下所示：有五种形态：(1)(2)(3)(4)(5)3分别写出图6-28(a)所示的二叉树的前序、中序和后序遍历序列。前序ABCDEF中序ACEDB后序EDCBA4画出图6-28(b)所示二叉树顺序存储和二叉链表的存储结构。BACDEABCDGEFHI(b)(a)图6-285请画出如图6-29所示两棵二叉树的顺序存储结构，并比较每棵二叉树所用的存储空间的大小。CBADLKMN图6-29 (a)

48、(b)(b) 所用的存储空间的大6一棵完全二叉树的第3层上有4个叶子结点，问该二叉树最多有多少个结点？7个结点7已知一棵二叉树只存在度数为0或度数为2的结点，度数为2的结点有19个，问度数为0的结点有多少个？20个，分析：根据公式n0=n2+1，有n0=19+1=208写出用非递归实现二叉树的中序遍历算法，并分析其时间复杂度和栈所需要的最大容量。二叉树的中序遍历的非递归算法。void Inorder2（BTNode *bt） /* 利用栈实现前序遍历非递归算法 */ p=bt；top=-1； while(p|top>-1) if(p) /* 二叉树非空 */ +top ；stop=p ；

49、 /*根结点指针进栈*/p=p->lchild ； /*p移向左孩子*/else /*栈非空*/ p=stop ；-top ； /*双亲结点指针出栈*/ printf(p->data)； /*访问根结点，输出结点*/ p=p->rchild ； /*p移向右孩子*/ /* Inorder2 */9若已知某二叉树的前序遍历序列为ABCDEFGHI和中序遍历序列为BCAEDGHFI，试画出该二叉树。并写出后序遍历的结果。ABDCHEFGI10设二叉树以二叉链表形式存储，写一算法交换各结点的左右子树。void Exchange1(BTNode *bt) /* 交换左右子树的第一种方

50、法*/ if(*bt) /* 这里以指针为参数使交换在实参结点上进行 */ BTNode p; Exchange1(&(*bt)->lchild); Exchange1(&(*bt)->rchild); p=(*bt)->lchild; (*bt)->lchild=(*bt)->rchild; (*bt)->rchild=p; void Exchange2(BTNode *bt) /*交换左右子树的第二种方法*/ if(bt) BTNode *p; p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; Exchange2(bt->lchild); Exchange2(bt->rchild); /* Exchange2 */11设二叉树以二叉链表形式存储，