1、精選優(yōu)質(zhì)文檔-傾情為你奉上蘭州大學(xué) 二叉樹第一題/二叉樹結(jié)點(diǎn)typedef struct BiTNode/數(shù)據(jù)char data;/左右孩子指針struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/按前序遍歷創(chuàng)建二叉樹int CreateBiTree(BiTree &T)char data;/按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），#表示空樹scanf("%c",&data);if(data = '#')T = NULL;elseT = (BiTree)malloc(sizeof(BiTNode)

2、;/生成根結(jié)點(diǎn)T->data = data;/構(gòu)造左子樹CreateBiTree(T->lchild);/構(gòu)造右子樹CreateBiTree(T->rchild);return 0; /輸出void Visit(BiTree T)if(T->data != '#')printf("%c ",T->data); /前序遍歷void PreOrder(BiTree T)if(T != NULL)/訪問根節(jié)點(diǎn)Visit(T);/訪問左子結(jié)點(diǎn)PreOrder(T->lchild);/訪問右子結(jié)點(diǎn)PreOrder(T->rch

3、ild); /中序遍歷void InOrder(BiTree T)if(T != NULL)/訪問左子結(jié)點(diǎn)InOrder(T->lchild);/訪問根節(jié)點(diǎn)Visit(T);/訪問右子結(jié)點(diǎn)InOrder(T->rchild); /后序遍歷void PostOrder(BiTree T)if(T != NULL)/訪問左子結(jié)點(diǎn)PostOrder(T->lchild);/訪問右子結(jié)點(diǎn)PostOrder(T->rchild);/訪問根節(jié)點(diǎn)Visit(T); 前序/先序遍歷：結(jié)果：特征：訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前中序遍歷：結(jié)果：特征：訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左

4、右子樹之中（間）后序遍歷：結(jié)果：特征：訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后第二題采用中序遍歷的結(jié)果：從大到小排序直接插入排序：void InsSort(int a, int k)int j;for(int i=1;i<k;i+)/循環(huán)從第2個(gè)元素開始if(ai > ai-1)int temp=ai;for(j=i-1;j>=0 && aj<temp;j-)aj+1=aj;aj+1=temp;/此處就是aj+1=temp; 冒泡排序：void BubbleSort(int a, int k)int i,j,temp; for(j=0;j<n-1;

5、j+)for(i=0;i<n-1-j;i+)if(ai<ai+1)temp=ai;ai=ai+1;ai+1=temp; void main()int a=4,2,7,5,1,3,6;int k=sizeof(a)/sizeof(a0);/數(shù)組大小InsSort(a, k);/直接插入排序for(int i=0; i<k;i+)printf("%d ", ai);printf("n"); int b=4,2,7,5,1,3,6;int n=sizeof(a)/sizeof(a0);/數(shù)組大小BubbleSort(b, n);/冒泡排序fo

6、r(int i=0; i<n;i+)printf("%d ", bi);printf("n");第三題直接插入排序：思想：最基本的插入排序，將第n個(gè)插入到前n-1個(gè)中的適當(dāng)位置時(shí)間復(fù)雜度：T(n) = O(n²)穩(wěn)定性：穩(wěn)定排序。循環(huán)條件(j>=0 && aj<temp)保證的冒泡排序：思想：反復(fù)掃描待排序序列，在掃描的過程中順次比較相鄰的兩個(gè)元素的大小，若逆序就交換位置。第一趟，從第一個(gè)數(shù)據(jù)開始，比較相鄰的兩個(gè)數(shù)據(jù)，（以升序?yàn)槔┤绻缶徒粨Q，得到一個(gè)最大數(shù)據(jù)在末尾；然后進(jìn)行第二趟，只掃描前n-1個(gè)元素，得到次大的放在倒數(shù)第二位。以此