兰州大学--数据结构-命题作业-二叉树(完整答案).doc
《兰州大学--数据结构-命题作业-二叉树(完整答案).doc》由会员分享,可在线阅读,更多相关《兰州大学--数据结构-命题作业-二叉树(完整答案).doc(6页珍藏版)》请在冰点文库上搜索。
兰州大学二叉树
第一题
//二叉树结点
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{
if(a[i]>a[i-1])
{
inttemp=a[i];
for(j=i-1;j>=0&&a[j]{
a[j+1]=a[j];
}
a[j+1]=temp;//此处就是a[j+1]=temp;
}
}
}
冒泡排序:
voidBubbleSort(inta[],intk)
{
inti,j,temp;
for(j=0;j{
for(i=0;i{
if(a[i]{
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{
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{
printf("%d",b[i]);
}
printf("\n");
}
第三题
直接插入排序:
思想:
最基本的插入排序,将第n个插入到前n-1个中的适当位置
时间复杂度:
T(n)=O(n²)
稳定性:
稳定排序。
循环条件(j>=0&&a[j]冒泡排序:
思想:
反复扫描待排序序列,在扫描的过程中顺次比较相邻的两个元素的大小,若逆序就交换位置。
第一趟,从第一个数据开始,比较相邻的两个数据,(以升序为例)如果大就交换,得到一个最大数据在末尾;然后进行第二趟,只扫描前n-1个元素,得到次大的放在倒数第二位。
以此类推,最后得到升序序列。
如果在扫描过程中,发现没有交换,说明已经排好序列,直接终止扫描。
所以最多进行n-1趟扫描
时间复杂度:
T(n)=O(n²)
稳定性:
稳定排序