兰州大学-数据结构-命题作业-二叉树

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

1、兰州大学-数据结构-命题作业-二叉树（完整答案）有二叉树如图1所示：（1）用三种遍历方法遍历二叉树，写岀遍历结果，并总结三种遍历方法的特征。（2）选择其中的一种遍历结果，采用至少两种排序方法将其按从夫到小的顺序心排列。a（3）简要比较和评价所选排序算法。心作业要求：“（1）排序方法需描述算法思路并用程序描述算法，程序请添加注释。（2）排序算法的评价和比较主要从复杂度入手。卩第一题〃二叉树结点typedefstructBiTNode{〃数据chardata;〃左右孩子指针structBiTNode*lchild,*rchild;}BiTNode,*BiTree;〃按前序遍历创建

2、二叉树intCreateBiTree（BiTree&T）{chardata;〃按先序次序输入二叉树中结点的值（一个字符），’#'表示空树scanf（ll%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"J^data

3、);}}〃前序遍历voidPreOrder(BiTreeT){if(T!=NULL){〃访问根节点Visit(T);〃访问左子结点PreOrder(T->lchild);〃访问右子结点PreOrder(T->rchild);〃屮序遍历voidInOrderfBiTreeT){if(T!=NULL){〃访问左子结点lnOrder(T->lchild);〃访问根节点Visit仃)；〃访问右子结点lnOrder(T->rchild);}}〃后序遍历voidPostOrder(BiTreeT){if(T!=NULL){〃访问左子结点PostOrder(T->lchild);〃访问右子

4、结点PostOrder(T->rchild);〃访问根节点Visit仃)；}}前序/先序遍历：结果：1245736特征：访问根结点的操作发生在遍历其左右子树Z前屮序遍历：结果：4275136特征：访问根结点的操作发生在遍历其左右子树之中(间)后序遍历：结果：4752631特征：访问根结点的操作发生在遍历其左右子树Z后第二题采用中序遍历的结果：4275136从大到小排序直接插入排序：voidInsSortfinta[,intk){intj;for(inti=l;ia[i-l]){inttemp=a[i];for(j=i-

5、l;j>=0&&a[j]

6、(inti=0;i=0&&a[j]

7、比较相邻的两个元素的大小，若逆序就交换位置。第一趟，从第一个数据开始，比较相邻的两个数据，(以升序为例)如果大就交换,得到一个最大数据在末尾；然后进行第二趟，只扫描前个元素，得到次大的放在倒数第二位。以此类推，最后得到升序序列。如果在扫描过程中，发现没有交换，说明已经排好序列，直接终止扫描。所以最多进行趟扫描时间复杂度：T(n)=O(n2)稳定性：稳定排序