兰州大学--数据结构-命题作业-二叉树(完整答案).doc
- 文档编号:360734
- 上传时间:2023-04-29
- 格式:DOC
- 页数:6
- 大小:55.50KB
兰州大学--数据结构-命题作业-二叉树(完整答案).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;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 兰州大学 数据结构 命题 作业 二叉 完整 答案