兰州大学数据结构命题作业二叉树完整答案考试学习

参考资料--一页眉页脚可删除兰州大学二叉树有二叉树如图1所示,用三种遍历方法遍历二叉树，写出遍历结果，并息结三种遍历方法的特征。aF选择其中的一种遍历结果，来用至少两种排序方法磐其按从•大到小的顺序中排列…・⑸…简要比较和评份所选排序算法…作业要求：。111排序方法需描述算法思路并用程序描述算法，程序请添加注释匕口121排序算法的评价和比较主要驮复杂度入手…「第一题〃二叉树结点typedefstructBiTNode{〃数据chardata;〃左右孩子指针structBiTNode*lchild,*rchild;}BiTNode,*BiTree;〃按前序遍历创建二叉树intCreateBiTree(BiTree&T){chardata;〃按先序次序输入二叉树中结点的值(一个字符)，‘#’表示空树学习练习#——参考资料——页眉页脚可删除scanf("%c",&data);if(data=='#'){T=NULL;)else{T=(BiTree)malloc(sizeof(BiTNode));〃生成根结点T->data=data;〃构造左子树CreateBiTree(T->lchild);〃构造右子树CreateBiTree(T->rchild);)return0;)〃输出voidVisit(BiTreeT){if(T->data!='#'){printf("%c",T->data);))〃前序遍历voidPreOrder(BiTreeT){if(T!=NULL){〃访问根节点Visit(T);〃访问左子结点学习练习#——参考资料——页眉页脚可删除PreOrder(T->lchild);〃访问右子结点PreOrder(T->rchild);))〃中序遍历voidInOrder(BiTreeT){if(T!=NULL){〃访问左子结点InOrder(T->lchild);〃访问根节点Visit(T);〃访问右子结点InOrder(T->rchild);))〃后序遍历voidPostOrder(BiTreeT){if(T!=NULL){〃访问左子结点PostOrder(T->lchild);〃访问右子结点PostOrder(T->rchild);〃访问根节点Visit(T);))学习练习#参考密料--一页眉页脚可删除前序/先序遍历：结果：1245736特征：访问根结点的操作发生在遍历其左右子树之前中序遍历：结果：4275136特征：访问根结点的操作发生在遍历其左右子树之中（间）后序遍历：结果：4752631特征：访问根结点的操作发生在遍历其左右子树之后第二题采用中序遍历的结果：4275136从大到小排序直接插入排序：voidInsSort(inta[],intk)(intj;for(inti=1;i<k;i++)//循环从第2个元素开始(if(a[i]>a[i-1])(inttemp=a[i];for(j=i-1;j>=0&&a[j]<temp;j--)(a[j+1]=a[j];)学习练习#—参考资料——页眉页脚可删除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]);//数组大小InsSort(a,k);//直接插入排序for(inti=0;i<k;i++)学习练习#—参考资料——页眉页脚可删除(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个插入到前n-1个中的适当位置时间复杂度：T(n)=O(n2)稳定性：稳定排序。循环条件(j>=0&&a[j]<temp)保证的冒泡排序：思想：反复扫描待排序序列，在扫描的过程中顺次比较相邻的两个元素的大小，若逆序就交换位置。第一趟，从第一个数据开始，比较相邻的两个数据,(以升序为例)如果大就交换，得到一个最大数据在末尾；然后进行第二趟，只扫描前n-1个元素，得到次大的放在倒数第学习练习#—