实验五--二叉树的建立及遍历.doc

《实验五--二叉树的建立及遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验五二叉树的建立及遍历一、实验目的1．熟悉二叉树的存贮结构及遍历方式，掌握有关算法的实现。2．能够利用二叉树解决具体问题。二、实验内容1.要求采用二叉链表作为存贮结构，树中每个结点的数据类型设定为字符型。完成二叉树的建立、先序、中序、和后序递归遍历的操作。2.利用栈实现非递归中序遍历二叉树。3.利用队列实现按层遍历二叉树。实现提示：本算法要采用一个队列q，先输出二叉树根结点，然后判断：若其左孩子指针非空，则将其入队列；若其右孩子指针非空，则也将其入队列。然后取队列首指针，对其所指结点继续做如上操作，直到队列空为止。因为队列的特点是先

2、进先出，从而达到按层次顺序遍历二叉树目的。#include#include#includetypedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;voidcreat(BiTree&T){//填充创建树的代码}voidpreorder(BiTreeT){//填充先序遍历代码}voidinorder(BiTreeT){\填充中序遍历代码}voidpostorder(BiTreeT){

3、填充后序遍历代码}main(){BiTreeT;creat(T);preorder(T);printf("");postorder(T);printf("");inorder(T);printf("");}实验六查找一、实验目的1．掌握顺序查找和折半查找两种查找的算法及实现技术；了解它们各自的优缺点。2．构造并能输出二叉排序树。3．熟悉上述查找方法的适用范围和条件，基本思想及效率分析。二、实验内容⒈顺序查找建立一个学生信息表，表中的每个数据元素是一个记录，其中的以学号作为关键字，编程进行顺序查找。如果找到，就输出该元素的

4、位置；如果没找到，输出0。#includetypedefstruct{intnu;charna[20];intscore;}elemtype;typedefstruct{elemtypeelem[20];intlength;}SSTable;intSearch_Seq(SSTableST,intkey){//顺序查找}voidmain(){SSTableST;intx=1,i,key;printf("Enterlength:");scanf("%d",&ST.length);for(i=1;i<=ST.lengt

5、h;i++){printf("No.%dnumber:",i);scanf("%d",&ST.elem[i].nu);printf("name:");scanf("%s",&ST.elem[i].na);printf("score:");scanf("%d",&ST.elem[i].score);}while(x==1){printf("Enterthenumbertosearch:");scanf("%d",&key);i=Search_Seq(ST,key);if(i>0){printf("Theelement

6、isno.%d:",i);printf("nu:%d,name:%s,score:%d",ST.elem[i].nu,ST.elem[i].na,ST.elem[i].score);}elseprintf("Thereisno%d",key);printf("1-Continue2-Out");scanf("%d",&x);}}⒉折半查找建立一个学生信息表，表中的每个数据元素是一个记录，要求表按关键字“学号”有序，编程实现折半查找。如果找到，就输出该元素的位置；如果没找到，输出0。#include

7、typedefstruct{intnu;charna[20];intscore;}elemtype;typedefstruct{elemtypeelem[20];intlength;}SSTable;intSearch_Bin(SSTableST,intkey){//填加折半查找的代码}voidmain(){SSTableST;intx=1,i,key;printf("Enterlength:");scanf("%d",&ST.length);for(i=1;i<=ST.length;i++){printf("No.%dnum

8、ber:",i);scanf("%d",&ST.elem[i].nu);printf("name:");scanf("%s",&ST.elem[i].na);printf("score:");scanf("%d"