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

《兰州大学 数据结构 命题作业 二叉树(完整答案).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、兰州大学二叉树第一题//二叉树结点typedefstructBiTNode{//数据chardata;//左右孩子指针structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//按前序遍历创建二叉树intCreateBiTree(BiTree&T){chardata;//按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树scanf("%c",&data);if(data=='#'){T=NULL;}else{T=(BiTree)malloc(sizeof(BiTNode

2、));//生成根结点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(

3、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

4、特征：访问根结点的操作发生在遍历其左右子树之前中序遍历：结果：4275136特征：访问根结点的操作发生在遍历其左右子树之中（间）后序遍历：结果：4752631特征：访问根结点的操作发生在遍历其左右子树之后第二题采用中序遍历的结果：4275136从大到小排序直接插入排序：voidInsSort(inta[],intk){intj;for(inti=1;ia[i-1]){inttemp=a[i];for(j=i-1;j>=0&&a[j]

5、j+1]=a[j];}a[j+1]=temp;//此处就是a[j+1]=temp;}}}冒泡排序：voidBubbleSort(inta[],intk){inti,j,temp;for(j=0;j

6、a,k);//直接插入排序for(inti=0;i

7、排序。循环条件(j>=0&&a[j]