【正文】 def Struct node { DateType data； Struct node * next； }ListNode； typedef ListNode * LinkList ； LinkList Leafhead=NULL； Void Inorder (BinTree T) { LinkList s； If(T){ Inorder(T－lchild)； If ((!T－lchild)amp。amp。(!T－rchild)){ s=(ListNode*)malloc(sizeof(ListNode))； s－data=T－data； s－next=Leafhead； Leafhead=s； } Inorder(T－rchild)； } } 對于如下所示的二叉樹 (1) 畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)；(2) 說明該算法的功能。中序建立線索二叉樹 已知一個算法設(shè)計如下：void ABC(BTNode * BT){ if BT { ABC (BTleft)。 ABC (BTright)。 coutBTdata39。 39。 } }問：該算法的功能是什么？后序遍歷二叉樹已知一個算法設(shè)計如下：void unkown(JD r[ ],int n){ int m,i,j,flag=1。 JD x。 m=n1。 while((m0)amp。amp。(flag==1)) { flag=0。 for(j=1。j=m。j++) if(r[j].keyr[j+1].key) { flag=1。 x=r[j]。 r[j]=r[j+1]。 r[j+1]=x。 } m。 }}問：該算法的功能是什么？冒泡法升序排列某個數(shù)組閱讀下面的算法typedef char Datatype。typedef Struct node {Datatype data。 Struct node *lchild,*rchild。} bitree。void createbitree(bitree *amp。bt){ char ch。 scanf(%c,amp。ch)。 if(ch= =39。39。) {bt=0。 return。}bt=(bitree*)malloc(sizeof(bitree))。btdata=ch。createbitree(btlchild)。 createbitree(btrchild)。}問：該算法的功能是什么？先序創(chuàng)建二叉樹閱讀下面的算法void Search(BTNode * BT){ if BT { Search(BTleft)。 Search(BTright)。 coutBTdata39。 39。 } }問：該算法的功能是什么？后序遍歷二叉樹六、算法填空題將二叉樹bt中每一個結(jié)點(diǎn)的左右子樹互換的C語言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進(jìn)隊(duì)、出隊(duì)和判別隊(duì)列是否為空的函數(shù)，請?zhí)顚懰惴ㄖ锌瞻字?，完成其功能。typedef struct node {int data 。 struct node *lchild, *rchild。 }btnode。 void EXCHANGE(btnode *bt){btnode *p, *q。 if (bt){ADDQ(Q,bt)。 //入隊(duì) while(!EMPTY(Q)) //隊(duì)不空，那么我們就出隊(duì) {p=DELQ(Q)。 if(plchild) _ (1) ADDQ(Q, plchild)__。 //左孩子不空，左孩子入隊(duì)if(prchild) _ (2) ADDQ(Q, prchild)__。 //右孩子不空，右孩子入隊(duì)//下面交換左右孩子q=_（3）prchild __。 // prchild=_（4）plchild __。 _ （5）plchild _=q。 } } } 下列算法將以二叉鏈表存儲的二叉樹中的葉子結(jié)點(diǎn)按從左到右的順序鏈成一個帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，鏈接時，結(jié)點(diǎn)的Lchild域作為前鏈域，指向結(jié)點(diǎn)的直接前驅(qū)，結(jié)點(diǎn)的Rchild域作為后鏈域，指向結(jié)點(diǎn)的直接后繼。算法中，使用一個順序棧stack，棧頂指針為top，p，t為輔助指針，head為雙向循環(huán)鏈表的頭指針。試填充算法中的空格，以完整算法。void leafchain(BiTree amp。bt){ p=(BiTree)malloc(sizeof(BiTNode))。 if(!p){printf(“OVERFLOW\n”。exit(1)。 } head=p。 top=1。 if(bt) //如果樹不為空 {top++。 stack[top]=bt。 // 入棧 while(top) //棧不空 { t=stack[top]。 top。 // 出棧 if(!tLchild amp。amp。 !tRchild) //該節(jié)點(diǎn)的左右孩子都為空，那么這是葉子節(jié)點(diǎn){//雙鏈表的創(chuàng)建操作 (1) pRchild = t 。 tLchild=p 。 (2) tRchild = NULL 。} else {if( (3) tLchild ){top++。 stack[top]= tRchild 。 }//如果有左孩子那么左孩子入棧 if( (4) tRchild ){top++。 stack[top]= (5) 。 }//如果有右孩子那么右孩子入棧 } } pRchild=head。 headLchild=p。 //構(gòu)成循環(huán)鏈表} }下列算法的功能是在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡單選擇排序，請在空白處填入適當(dāng)?shù)膬?nèi)容。void simpleselectsorlklist(lklist *amp。head){ lklist *p,*q,*s。 int min, t。 if(head==0 ||headnext==0) return。//如果為空表或只有一個節(jié)點(diǎn)，不用排序了 for(q=head。 q!=0。q=qnext) //只要節(jié)點(diǎn)存在，那么一直向后移動 //此時的q一直指向亂序的第一個位置 { （1）min = qdata ； //min賦初值s=q。 //s指向無序的第一個元素 for(p=qnext。 p!=0。p=pnext) //p從s的下一個位置開始找if(minpdata) //如果發(fā)現(xiàn)有一個比這些亂序中的第一個元素，那么s指向這個最小的值，同時min我們也要變成這個值{ （2）min = pdata ； s=p。} if(s!=q) //如果這個最小值不在我們的亂序的第一個位置，那么我們就變換位置，讓這個最小值變到無序序列的第一個位置，然后我們的有序序列就又多了一個成員 //下面實(shí)現(xiàn)交換。此時q指向無序序列的第一個位置，即我們要變成最小值的位置s指向我們最小值的位置。{ （3）min = sdata ； （4） sdata = qdata ； （5） qdata = min ； } }}下列算法的功能是比較兩個鏈串的大小，其返回值為： 請在空白處填入適當(dāng)?shù)膬?nèi)容。int str(LinkString s1,LinkString s2) {//s1和s2為兩個鏈串的頭指針 while(s1amp。amp。s2){ if(s1dates2date) return 1； if(s1dates2date) return1； （1）s1 = s1next ； （2）s2 = s2next ； } if( （3）(!s1)amp。amp。s2 ) return 1；//s1短些 if( （4）s1amp。amp。(!s2) ) return 1；//s1長些 （5） return 0 ； //一樣長且一直不大于也不小于 }