兰州大学--数据结构-命题作业-二叉树(完整答案)

兰州大学二叉树第一题//二叉树结点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;ik;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;jn-1;j++){for(i=0;in-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;ik;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;in;i++){printf(%d,b[i]);}printf(\n);}第三题直接插入排序：思想：最基本的插入排序，将第n个插入到前n-1个中的适当位置时间复杂度：T(n)=O(n²)稳定性：稳定排序。循环条件(j=0&&a[j]temp)保证的冒泡排序：思想：反复扫描待排序序列，在扫描的过程中顺次比较相邻的两个元素的大小，若逆序就交换位置。第一趟，从第一个数据开始，比较相邻的两个数据，（以升序为例）如果大就交换，得到一个最大数据在末尾；然后进行第二趟，只扫描前n-1个元素，得到次大的放在倒数第二位。以此类推，最后得到升序序列。如果在扫描过程中，发现没有交换，说明已经排好序列，直接终止扫描。所以最多进行n-1趟扫描时间复杂度：T(n)=O(n²)稳定性：稳定排序