兰州大学--数据结构-命题作业-二叉树(完整答案)Word文档下载推荐.doc
《兰州大学--数据结构-命题作业-二叉树(完整答案)Word文档下载推荐.doc》由会员分享，可在线阅读，更多相关《兰州大学--数据结构-命题作业-二叉树(完整答案)Word文档下载推荐.doc（6页珍藏版）》请在冰点文库上搜索。
%c"
&
data）;
if（data=='
#'
）{
T=NULL;
}
else{
T=（BiTree）malloc（sizeof（BiTNode））;
//生成根结点
T->
data=data;
//构造左子树
CreateBiTree（T->
lchild）;
//构造右子树
rchild）;
return0;
//输出
voidVisit（BiTreeT）{
if（T->
data!
='
printf（"
%c"
T->
//前序遍历
voidPreOrder（BiTreeT）{
if（T!
=NULL）{
//访问根节点
Visit（T）;
//访问左子结点
PreOrder（T->
//访问右子结点
//中序遍历
voidInOrder（BiTreeT）{
InOrder（T->
//后序遍历
voidPostOrder（BiTreeT）{
PostOrder（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;
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<
%d"
a[i]）;
\n"
）;
intb[]={4,2,7,5,1,3,6};
intn=sizeof（a）/sizeof（a[0]）;
BubbleSort（b,n）;
//冒泡排序
n;
b[i]）;
第三题
思想：
最基本的插入排序，将第n个插入到前n-1个中的适当位置
时间复杂度：
T（n）=O（n²
）
稳定性：
稳定排序。
循环条件（j>
temp）保证的
反复扫描待排序序列，在扫描的过程中顺次比较相邻的两个元素的大小，若逆序就交换位置。
第一趟，从第一个数据开始，比较相邻的两个数据，（以升序为例）如果大就交换，得到一个最大数据在末尾；
然后进行第二趟，只扫描前n-1个元素，得到次大的放在倒数第二位。
以此类推，最后得到升序序列。
如果在扫描过程中，发现没有交换，说明已经排好序列，直接终止扫描。
所以最多进行n-1趟扫描
稳定排序
升级会员 