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

《兰州大学--数据结构-命题作业-二叉树(完整答案)(共6页).doc》由会员分享，可在线阅读，更多相关《兰州大学--数据结构-命题作业-二叉树(完整答案)(共6页).doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上兰州大学 二叉树第一题/二叉树结点typedef struct BiTNode/数据char data;/左右孩子指针struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/按前序遍历创建二叉树int CreateBiTree(BiTree &T)char data;/按先序次序输入二叉树中结点的值（一个字符），#表示空树scanf(%c,&data);if(data = #)T = NULL;elseT = (BiTree)malloc(sizeof(BiTNode);/生成根结点T-data = data;/构造左子树Cre

2、ateBiTree(T-lchild);/构造右子树CreateBiTree(T-rchild);return 0; /输出void Visit(BiTree T)if(T-data != #)printf(%c ,T-data); /前序遍历void PreOrder(BiTree T)if(T != NULL)/访问根节点Visit(T);/访问左子结点PreOrder(T-lchild);/访问右子结点PreOrder(T-rchild); /中序遍历void InOrder(BiTree T)if(T != NULL)/访问左子结点InOrder(T-lchild);/访问根节点Vis

3、it(T);/访问右子结点InOrder(T-rchild); /后序遍历void PostOrder(BiTree T)if(T != NULL)/访问左子结点PostOrder(T-lchild);/访问右子结点PostOrder(T-rchild);/访问根节点Visit(T); 前序/先序遍历：结果：特征：访问根结点的操作发生在遍历其左右子树之前中序遍历：结果：特征：访问根结点的操作发生在遍历其左右子树之中（间）后序遍历：结果：特征：访问根结点的操作发生在遍历其左右子树之后第二题采用中序遍历的结果：从大到小排序直接插入排序：void InsSort(int a, int k)int j

4、;for(int i=1;i ai-1)int temp=ai;for(j=i-1;j=0 & ajtemp;j-)aj+1=aj;aj+1=temp;/此处就是aj+1=temp; 冒泡排序：void BubbleSort(int a, int k)int i,j,temp; for(j=0;jn-1;j+)for(i=0;in-1-j;i+)if(aiai+1)temp=ai;ai=ai+1;ai+1=temp; void main()int a=4,2,7,5,1,3,6;int k=sizeof(a)/sizeof(a0);/数组大小InsSort(a, k);/直接插入排序for(i

5、nt i=0; ik;i+)printf(%d , ai);printf(n); int b=4,2,7,5,1,3,6;int n=sizeof(a)/sizeof(a0);/数组大小BubbleSort(b, n);/冒泡排序for(int i=0; i=0 & ajtemp)保证的冒泡排序：思想：反复扫描待排序序列，在扫描的过程中顺次比较相邻的两个元素的大小，若逆序就交换位置。第一趟，从第一个数据开始，比较相邻的两个数据，（以升序为例）如果大就交换，得到一个最大数据在末尾；然后进行第二趟，只扫描前n-1个元素，得到次大的放在倒数第二位。以此类推，最后得到升序序列。如果在扫描过程中，发现没有交换，说明已经排好序列，直接终止扫描。所以最多进行n-1趟扫描时间复杂度：T(n) = O(n)稳定性：稳定排序专心-专注-专业