蘭州大學(xué)數(shù)據(jù)結(jié)構(gòu)命題作業(yè)二叉樹(shù)完整答案考試學(xué)習(xí)

參考資料--一頁(yè)眉頁(yè)腳可刪除蘭州大學(xué)二叉樹(shù)有二叉樹(shù)如圖1所示,用三種遍歷方法遍歷二叉樹(shù)，寫出遍歷結(jié)果，并息結(jié)三種遍歷方法的特征。aF選擇其中的一種遍歷結(jié)果，來(lái)用至少兩種排序方法磐其按從?大到小的順序中排列…?⑸…簡(jiǎn)要比較和評(píng)份所選排序算法…作業(yè)要求：。111排序方法需描述算法思路并用程序描述算法，程序請(qǐng)?zhí)砑幼⑨屫翱?21排序算法的評(píng)價(jià)和比較主要馱復(fù)雜度入手…「第一題〃二叉樹(shù)結(jié)點(diǎn)typedefstructBiTNode{〃數(shù)據(jù)chardata;〃左右孩子指針structBiTNode*lchild,*rchild;}BiTNode,*BiTree;〃按前序遍歷創(chuàng)建二叉樹(shù)intCreateBiTree(BiTree&T){chardata;〃按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值(一個(gè)字符)，‘#’表示空樹(shù)學(xué)習(xí)練習(xí)#——參考資料——頁(yè)眉頁(yè)腳可刪除scanf("%c",&data);if(data=='#'){T=NULL;)else{T=(BiTree)malloc(sizeof(BiTNode));〃生成根結(jié)點(diǎn)T->data=data;〃構(gòu)造左子樹(shù)CreateBiTree(T->lchild);〃構(gòu)造右子樹(shù)CreateBiTree(T->rchild);)return0;)〃輸出voidVisit(BiTreeT){if(T->data!='#'){printf("%c",T->data);))〃前序遍歷voidPreOrder(BiTreeT){if(T!=NULL){〃訪問(wèn)根節(jié)點(diǎn)Visit(T);〃訪問(wèn)左子結(jié)點(diǎn)學(xué)習(xí)練習(xí)#——參考資料——頁(yè)眉頁(yè)腳可刪除PreOrder(T->lchild);〃訪問(wèn)右子結(jié)點(diǎn)PreOrder(T->rchild);))〃中序遍歷voidInOrder(BiTreeT){if(T!=NULL){〃訪問(wèn)左子結(jié)點(diǎn)InOrder(T->lchild);〃訪問(wèn)根節(jié)點(diǎn)Visit(T);〃訪問(wèn)右子結(jié)點(diǎn)InOrder(T->rchild);))〃后序遍歷voidPostOrder(BiTreeT){if(T!=NULL){〃訪問(wèn)左子結(jié)點(diǎn)PostOrder(T->lchild);〃訪問(wèn)右子結(jié)點(diǎn)PostOrder(T->rchild);〃訪問(wèn)根節(jié)點(diǎn)Visit(T);))學(xué)習(xí)練習(xí)#參考密料--一頁(yè)眉頁(yè)腳可刪除前序/先序遍歷：結(jié)果：1245736特征：訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之前中序遍歷：結(jié)果：4275136特征：訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之中（間）后序遍歷：結(jié)果：4752631特征：訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之后第二題采用中序遍歷的結(jié)果：4275136從大到小排序直接插入排序：voidInsSort(inta[],intk)(intj;for(inti=1;i<k;i++)//循環(huán)從第2個(gè)元素開(kāi)始(if(a[i]>a[i-1])(inttemp=a[i];for(j=i-1;j>=0&&a[j]<temp;j--)(a[j+1]=a[j];)學(xué)習(xí)練習(xí)#—參考資料——頁(yè)眉頁(yè)腳可刪除a[j+1]=temp;〃止匕處就是a[j+1]=temp;)))冒泡排序：voidBubbleSort(inta[],intk)(inti,j,temp;for(j=0;j<n-1;j++)(for(i=0;i<n-1-j;i++)(if(a[i]<a[i+1])(temp=a[i];a[i]=a[i+1];a[i+1]=temp;))))voidmain()(inta[]={4,2,7,5,1,3,6};intk=sizeof(a)/sizeof(a[0]);//數(shù)組大小InsSort(a,k);//直接插入排序for(inti=0;i<k;i++)學(xué)習(xí)練習(xí)#—參考資料——頁(yè)眉頁(yè)腳可刪除(printf("%d",a[i]);)printf("\n");intb[]={4,2,7,5,1,3,6};intn=sizeof(a)/sizeof(a[0]);/微組大小BubbleSort(b,n);//冒泡排序for(inti=0;i<n;i++){printf("%d",b[i]);}printf("\n");}第三題直接插入排序：思想：最基本的插入排序，將第n個(gè)插入到前n-1個(gè)中的適當(dāng)位置時(shí)間復(fù)雜度：T(n)=O(n2)穩(wěn)定性：穩(wěn)定排序。循環(huán)條件(j>=0&&a[j]<temp)保證的冒泡排序：思想：反復(fù)掃描待排序序列，在掃描的過(guò)程中順次比較相鄰的兩個(gè)元素的大小，若逆序就交換位置。第一趟，從第一個(gè)數(shù)據(jù)開(kāi)始，比較相鄰的兩個(gè)數(shù)據(jù),(以升序?yàn)槔?如果大就交換，得到一個(gè)最大數(shù)據(jù)在末尾；然后進(jìn)行第二趟，只掃描前n-1個(gè)元素，得到次大的放在倒數(shù)第學(xué)習(xí)練習(xí)#—