华南农业大学信息学院数据结构--课程设计报告

华南农业大学信息学院

设计性、综合性实验

学院 实 验 题 目 起止日期:______ 信息学院 专业班级 学号 姓名 实现二叉排序树的各种算法<一> 项 目 算法设计 成功 失败 独立完成情况 独立 √ √ √ √ √ √ √ √ √ √设计性 □综合性 算法熟练程度 掌握 了解 不懂 √ √ √ √ √ √ √ √ √ 帮助 测试通过 √ √ √ √ √ √ √ √ √ 创建一棵空的二叉排序树 自 我 评 价 插入新结点 前序、中序、后序遍历二叉树 中序遍历的非递归算法 层次遍历二叉树 在二叉树中查找给定关键字 交换各结点的左右子树（选做） 求二叉树的深度（选做） 叶子结点数（选做） 输出树型结构（选做） 成绩 √ √ √ √ √ √ √ √ √ ? A---------完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码符合书写规范，实验报告叙述清晰完整，有详尽的分析和总结。 ? B---------完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述 清晰完整。 ? C---------完成实验要求的大部分功能，实验报告良好。 ? D---------未按时完成实验，或者抄袭。 教师签名:______

实验四上机实习报告

专业班级:___________ 学号：_________ 姓名:______ 完成日期:_______

（1） 问题的描述：

用函数实现如下二叉排序树算法： （1） 插入新结点

（2） 前序、中序、后序遍历二叉树 （3） 中序遍历的非递归算法 （4） 层次遍历二叉树

（5） 在二叉树中查找给定关键字(函数返回值为成功1,失败0) Input

第一行：准备建树的结点个数n 第二行：输入n个整数，用空格分隔 第三行：输入待查找的关键字 第四行：输入待查找的关键字 第五行：输入待插入的关键字 Output

第一行：二叉树的先序遍历序列 第二行：二叉树的中序遍历序列 第三行：二叉树的后序遍历序列 第四行：查找结果 第五行：查找结果

第六行~第八行：插入新结点后的二叉树的先、中、序遍历序列 第九行：插入新结点后的二叉树的中序遍历序列(非递归算法) 第十行：插入新结点后的二叉树的层次遍历序列 （2） 数据结构的设计：

为了方便移动使用链表来存储二叉树，因此设计如下数据类型表示二叉树： typedef struct BiTNode //生成树的结构体 { ElemType key; //存储数据 struct BiTNode *left,*right; //左、右孩子指针 }BiTNode,*BiTree;

int main() //主函数 { BiTree T; ElemType search1,search2,insert; T=CreateBiTree(); //建立二叉树 scanf(\ PreOrderTraverse(T); //先序遍历 printf(\ InOrderTraverse(T); //中序遍历

}

printf(\

PostOrderTraverse(T); //后序遍历 printf(\

if(searchBiT(T,search1)==NULL)//查找函数 printf(\else printf(\ //对第一个关键字进行查找 if(searchBiT(T,search2)==NULL) printf(\else printf(\ //对第二个关键字进行查找 T=InsertBiT(T,insert); //插入一个新结点 PreOrderTraverse(T); //对插入后的新树进行先序遍历 printf(\

InOrderTraverse(T); //对插入后的新树进行中序遍历 printf(\

PostOrderTraverse(T); //对插入后的新树进行后序遍历 printf(\

InOrderTraverseII(T); //对插入后的新树进行中序遍历（非递归算法） printf(\

LevelOrderTraverse(T); //对插入后的新树进行层次遍历 return 0;

（3） 函数功能、参数说明及概要设计：

1、CreateBiTree();//创建二叉树函数，返回成功与否。

//根据二叉排序树的特点，找出新结点在树中对应的位置，再插入树中。 2、PreOrderTraverse(T);//用递归方式，前序遍历。 3、InOrderTraverse(T); //用递归方式，中序遍历。 4、PostOrderTraverse(T);//用递归方式，后序遍历。

5、InOrderTraverseII(T);//利用栈，用非递归方式，返回成功与否。

//先扫描（非访问）根节点到所有左节点并将它们一一入栈，当无左节点时表示栈顶节点无左子树，然后取出这个节点，并访问它，将P指向刚出栈的节点到右孩子对右孩子进行同样的处理。

6、searchBiT(T,search1);//查找函数，递归算法，返回成功与否。 //利用中序遍历二叉树T，依次比较每个结点的关键字。 7、InsertBiT(T,insert);//插入函数，返回成功与否。

8、LevelOrderTraverse(T);//利用队列，层次遍历，返回成功与否。

//将根节点入队，循环执行，出队，访问该节点，若该节点的左子节点不为空则将该节点的左子节点入队，若该节点的右子节点不为空，则该节点的右子节点入队；直到队列为空。 （4） 具体程序的实现 #include

#include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define STACK_INIT_SIZE 100 // 存储空间初始分配量 #define STACKINCREMENT 10 // 存储空间分配增量

typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int ElemType; //定义元素类型

typedef struct BiTNode //生成树的结构体 { ElemType key; struct BiTNode *left,*right;//左右孩子指针 }BiTNode,*BiTree;

BiTree InsertBiT(BiTree T,ElemType key) { //向树中写入数据，插入数据元素key BiTree f,p=T; while(p) { if(p->key==key) return NULL; f=p; p=(keykey)?p->left:p->right; } p=(BiTree)malloc(sizeof(BiTNode)); p->key=key; p->left=p->right=NULL; if(T==NULL) T=p; else if(keykey) f->left=p; else f->right=p; return T; }

BiTree CreateBiTree() { //生成二叉树 BiTree T=NULL; ElemType key;

int n,i; scanf(\ for(i=1;i<=n;i++) { scanf(\ T=InsertBiT(T,key); //向树中插入数据 } return T; }

void PreOrderTraverse(BiTree root) { BiTree p=root; //先序遍历，递归算法 if(p!=NULL) { printf(\ PreOrderTraverse(p->left); PreOrderTraverse(p->right); } }

void InOrderTraverse(BiTree root) { //中序遍历，递归算法 BiTree p=root; if(p!=NULL){ InOrderTraverse(p->left ); printf(\ InOrderTraverse(p->right ); } }

void PostOrderTraverse(BiTree root) { //后序遍历，递归算法 BiTree p=root; if(p!=NULL) { PostOrderTraverse(p->left ); PostOrderTraverse(p->right ); printf(\ } }

Status visit(BiTree p) //输出结点的值 {