1、請設計一個算法，要求該算法把二叉樹的葉子結點按從左到右的順序連成一個單鏈表，表頭指針為head。二叉樹按二叉鏈表方式存儲，鏈接時用葉子結點的右指針域來存放單鏈表指針。分析你的算法的時、空復雜度。2、將頂點放在兩個集合V1和V2。對每個頂點，檢查其和鄰接點是否在同一個集合中，如是，則為非二部圖。為此，用整數1和2表示兩個集合。再用一隊列結構存放圖中訪問的頂點。intBPGraph(AdjMatrixg)//判斷以鄰接矩陣表示的圖g是否是二部圖。{ints[];//頂點向量，元素值表示其屬于那個集合（值1和2表示兩個集合）intQ[];//Q為隊列，元素為圖的頂點，這里設頂點信息就是頂點編號。intf=0,r,visited[];//f和r分別是隊列的頭尾指針,visited[]是訪問數組for(i=1;i<=n;i++){visited[i]=0;s[i]=0;}//初始化，各頂點未確定屬于那個集合Q[1]=1;r=1;s[1]=1;//頂點1放入集合S1while(f<r){v=Q[++f];if(s[v]==1)jh=2;elsejh=1;//準備v的鄰接點的集合號if(!visited[v]){visited[v]=1;//確保對每一個頂點，都要檢查與其鄰接點不應在一個集合中for(j=1,j<=n;j++)if(g[v][j]==1){if(!s[j]){s[j]=jh;Q[++r]=j;}//鄰接點入隊列elseif(s[j]==s[v])return(0);}//非二部圖}//if(!visited[v])}//whilereturn(1);}//是二部圖[算法討論]題目給的是連通無向圖，若非連通，則算法要修改。3、由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實現由已知某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹并打印出后序遍歷序列，請寫出程序所缺的語句。#defineMAX100typedefstructNode{charinfo;structNode*llink,*rlink;}TNODE;charpred[MAX],inod[MAX];main(intargc,int**argv){TNODE*root;if(argc<3)exit0;strcpy(pred,argv[1]);strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE*restore(char*ppos,char*ipos,intn){TNODE*ptr；char*rpos;intk;if(n<=0)returnNULL;ptr->info=(1)_______;for((2)_______;rpos<ipos+n;rpos++)if(*rpos==*ppos)break;k=(3)_______;ptr->llink=restore(ppos+1,(4)_______,k);ptr->rlink=restore((5)_______+k,rpos+1,n-1-k);returnptr;}postorder(TNODE*ptr){if(ptr=NULL)return;postorder(ptr->llink);postorder(ptr->rlink);printf(“%c”,ptr->info);}4、請編寫一個判別給定二叉樹是否為二叉排序樹的算法，設二叉樹用llink-rlink法存儲。5、連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊，最小生成樹是邊上權值之和最小的生成樹。故可按權值從大到小對邊進行排序，然后從大到小將邊刪除。每刪除一條當前權值最大的邊后，就去測試圖是否仍連通，若不再連通，則將該邊恢復。若仍連通，繼續向下刪；直到剩n-1條邊為止。voidSpnTree(AdjListg)//用“破圈法”求解帶權連通無向圖的一棵最小代價生成樹。{typedefstruct{inti,j,w}node;//設頂點信息就是頂點編號，權是整型數nodeedge[];scanf("%d%d",&e,&n);//輸入邊數和頂點數。for(i=1;i<=e;i++)//輸入e條邊：頂點，權值。scanf("%d%d%d",&edge[i].i,&edge[i].j,&edge[i].w);for(i=2;i<=e;i++)//按邊上的權值大小，對邊進行逆序排序。{edge[0]=edge[i];j=i-1;while(edge[j].w<edge[0].w)edge[j+1]=edge[j--];edge[j+1]=edge[0];}//fork=1;eg=e;while(eg>=n)//破圈，直到邊數e=n-1.{if(connect(k))//刪除第k條邊若仍連通。{edge[k].w=0;eg--;}//測試下一條邊edge[k]，權值置0表示該邊被刪除k++;//下條邊}//while}//算法結束。connect()是測試圖是否連通的函數，可用圖的遍歷實現，6、連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊，最小生成樹是邊上權值之和最小的生成樹。故可按權值從大到小對邊進行排序，然后從大到小將邊刪除。每刪除一條當前權值最大的邊后，就去測試圖是否仍連通，若不再連通，則將該邊恢復。若仍連通，繼續向下刪；直到剩n-1條邊為止。voidSpnTree(AdjListg)//用“破圈法”求解帶權連通無向圖的一棵最小代價生成樹。{typedefstruct{inti,j,w}node;//設頂點信息就是頂點編號，權是整型數nodeedge[];typedefstruct{BiTreet;inttag;//tag=0表示結點的左子女已被訪問，tag=1表示結點的右子女已被訪問}stack;stacks[],s1[];//棧，容量夠大BiTreeAncestor(BiTreeROOT,p,q,r)//求二叉樹上結點p和q的最近的共同祖先結點r。{top=0;bt=ROOT;while(bt!=null||top>0){while(bt!=null&&bt!=p&&bt!=q)//結點入棧{s[++top].t=bt;s[top].tag=0;bt=bt->lchild;}//沿左分枝向下if(bt==p)//不失一般性，假定p在q的左側,遇結點p時，棧中元素均為p的祖先結點{for(i=1;i<=top;i++)s1[i]=s[i];top1=top;}//將棧s的元素轉入輔助棧s1保存if(bt==q)//找到q結點。for(i=top;i>0;i--)//；將棧中元素的樹結點到s1去匹配{pp=s[i].t;for(j=top1;j>0;j--)if(s1[j].t==pp){printf(“p和q的最近共同的祖先已找到”)；return(pp);}｝while(top!=0&&s[top].tag==1)top--;//退棧if(top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝//沿右分枝向下遍歷}//結束while(bt!=null||top>0)return(null);//ｑ、p無公共祖先｝//結束Ancestor11、假設以I和O分別表示入棧和出棧操作。棧的初態和終態均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分）（1）下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO（2）通過對（1）的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數組中）。12、由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實現由已知某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹并打印出后序遍歷序列，請寫出程序所缺的語句。#defineMAX100typedefstructNode{charinfo;structNode*llink,*rlink;}TNODE;charpred[MAX],inod[MAX];main(intargc,int**argv){TNODE*root;if(argc<3)exit0;strcpy(pred,argv[1]);strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE*restore(char*ppos,char*ipos,intn){TNODE*ptr；char*rpos;intk;if(n<=0)returnNULL;ptr->info=(1)_______;for((2)_______;rpos<ipos+n;rpos++)if(*rpos==*ppos)break;k=(3)_______;ptr->llink=restore(ppos+1,(4)_______,k);ptr->rlink=restore((5)_______+k,rpos+1,n-1-k);returnptr;}postorder(TNODE*ptr){if(ptr=NULL)return;postorder(ptr->llink);postorder(ptr->rlink);printf(“%c”,ptr->info);}13、對一般二叉樹，僅根據一個先序、中序、后序遍歷，不能確定另一個遍歷序列。但對于滿二叉樹，任一結點的左右子樹均含有數量相等的結點，根據此性質，可將任一遍歷序列轉為另一遍歷序列（即任一遍歷序列均可確定一棵二叉樹）。voidPreToPost(ElemTypepre[],post[],intl1,h1,l2,h2)//將滿二叉樹的先序序列轉為后序序列，l1,h1,l2,h2是序列初始和最后結點的下標。{if(h1>=l1){post[h2]=pre[l1];//根結點half=(h1-l1)/2;//左或右子樹的結點數PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1)//將左子樹先序序列轉為后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1)//將右子樹先序序列轉為后序序列}}//PreToPost32..葉子結點只有在遍歷中才能知道，這里使用中序遞歸遍歷。設置前驅結點指針pre，初始為空。第一個葉子結點由指針head指向，遍歷到葉子結點時，就將它前驅的rchild指針指向它，最后葉子結點的rchild為空。LinkedListhead,pre=null;//全局變量LinkedListInOrder(BiTreebt)//中序遍歷二叉樹bt，將葉子結點從左到右鏈成一個單鏈表，表頭指針為head{if(bt){InOrder(bt->lchild);//中序遍歷左子樹if(bt->lchild==null&&bt->rchild==null)//葉子結點if(pre==null){head=bt;pre=bt;}//處理第一個葉子結點else{pre->rchild=bt;pre=bt;}//將葉子結點鏈入鏈表InOrder(bt->rchild);//中序遍歷左子樹pre->rchild=null;//設置鏈表尾}return(head);}//InOrder時間復雜度為O(n),輔助變量使用head和pre,棧空間復雜度O(n)14、因為后序遍歷棧中保留當前結點的祖先的信息，用一變量保存棧的最高棧頂指針，每當退棧時，棧頂指針高于保存最高棧頂指針的值時，則將該棧倒入輔助棧中，輔助棧始終保存最長路徑長度上的結點，直至后序遍歷完畢，則輔助棧中內容即為所求。voidLongestPath(BiTreebt)//求二叉樹中的第一條最長路徑長度{BiTreep=bt,l[],s[];//l,s是棧，元素是二叉樹結點指針，l中保留當前最長路徑中的結點inti，top=0,tag[],longest=0;while(p||top>0){while(p){s[++top]=p；tag[top]=0;p=p->Lc;}//沿左分枝向下if(tag[top]==1)//當前結點的右分枝已遍歷{if(!s[top]->Lc&&!s[top]->Rc)//只有到葉子結點時，才查看路徑長度if(top>longest){for(i=1;i<=top;i++)l[i]=s[i];longest=top;top--;}//保留當前最長路徑到l棧，記住最高棧頂指針，退棧}elseif(top>0){tag[top]=1;p=s[top].Rc;}//沿右子分枝向下}//while(p!=null||top>0)}//結束LongestPath15、假設以鄰接矩陣作為圖的存儲結構，編寫算法判別在給定的有向圖中是否存在一個簡單有向回路，若存在，則以頂點序列的方式輸出該回路（找到一條即可）。（注：圖中不存在頂點到自己的?。┯邢驁D判斷回路要比無向圖復雜。利用深度優先遍歷，將頂點分成三類：未訪問；已訪問但其鄰接點未