《华南农业大学信息学院数据结构》由会员分享，可在线阅读，更多相关《华南农业大学信息学院数据结构（15页珍藏版）》请在金锄头文库上搜索。
1、华南农业大学信息学院设计性、综合性实验起止日期:学院信息学院专业班级学号姓名实 验 题 目实现二叉排序树的各种算法一J设计性综合性自 我 评 价项目算法设计独立完成情况算法熟练程度测试 通过成功失败独立帮助掌握了解不懂创建一棵空的二叉排序树VVVV插入新结点VVVV前序、中序、后序遍历二叉树VVVV中序遍历的非递归算法VVVV层次遍历二叉树VVVV在二叉树中查找给定关键字VVVV父换各结点的左右子树（选做）VVVV求二叉树的深度（选做）VVVV叶子结点数（选做）VVVV输出树型结构（选做）成 绩 A完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码符合书写规范，实验报告叙述清晰完整，
2、有详尽的分析和总结。 B完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述清晰完整。 C完成实验要求的大部分功能，实验报告良好。 D未按时完成实验，或者抄袭。教师签名:实验四上机实习报告专业班级:学号： 姓名: 完成日期:1）问题的描述：用函数实现如下二叉排序树算法：（1）插入新结点（2）前序、中序、后序遍历二叉树（3）中序遍历的非递归算法（4）层次遍历二叉树（5）在二叉树中查找给定关键字（函数返回值为成功1,失败 0）Input第一行：准备建树的结点个数n第二行：输入 n 个整数，用空格分隔 第三行：输入待查找的关键字 第四行：输入待查找的关键字 第五行：输入待插入的关键字Outpu
3、t第一行：二叉树的先序遍历序列第二行：二叉树的中序遍历序列第三行：二叉树的后序遍历序列第四行：查找结果第五行：查找结果第六行第八行：插入新结点后的二叉树的先、中、序遍历序列 第九行：插入新结点后的二叉树的中序遍历序列（非递归算法） 第十行：插入新结点后的二叉树的层次遍历序列（2）数据结构的设计： 为了方便移动使用链表来存储二叉树，因此设计如下数据类型表示二叉树 typedef struct BiTNode/生成树的结构体ElemType key;/存储数据struct BiTNode *left,*right; /左、右孩子指针 BiTNode,*BiTree;int main（）/主函数Bi
4、Tree T;ElemType search1,search2,insert;T=CreateBiTree（）;/建立二叉树scanf（%d %d %d,&search1,&search2,&insert）;PreOrderTraverse（T）;/先序遍历printf（n）;InOrderTraverse（T）;/中序遍历printf(n);PostOrderTraverse(T);/后序遍历printf(n);if(searchBiT(T,searchl)=NULL)/ 查找函数printf(0n);elseprintf(ln);/对第一个关键字进行查找if(searchBiT(T,sea
5、rch2)=NULL)printf(0n);elseprintf(ln);/对第二个关键字进行查找T=InsertBiT(T,insert);/插入一个新结点PreOrderTraverse(T);/对插入后的新树进行先序遍历printf(n);InOrderTraverse(T);/对插入后的新树进行中序遍历printf(n);PostOrderTraverse(T);/对插入后的新树进行后序遍历printf(n);InOrderTraverseII(T);/对插入后的新树进行中序遍历(非递归算法)printf(n);LevelOrderTraverse(T);/对插入后的新树进行层次遍历r
6、eturn 0;(3) 函数功能、参数说明及概要设计：1、CreateBiTree()；/创建二叉树函数，返回成功与否。/根据二叉排序树的特点，找出新结点在树中对应的位置，再插入树中。2、PreOrderTraverse(T)；/用递归方式，前序遍历。3、InOrderTraverse(T); /用递归方式，中序遍历。4、PostOrderTraverse(T)；/用递归方式，后序遍历。5、InOrderTraversen(T);/利用栈，用非递归方式，返回成功与否。/先扫描(非访问)根节点到所有左节点并将它们一一入栈，当无左节点时表示栈顶节点无 左子树，然后取出这个节点，并访问它，将P指向刚
7、出栈的节点到右孩子对右孩子进行同样 的处理。6、searchBiT(T,search1)；/查找函数，递归算法，返回成功与否。利用中序遍历二叉树T,依次比较每个结点的关键字。7、InsertBiT(T,insert)；/插入函数，返回成功与否。8、LevelOrderTraverse(T)；/利用队列，层次遍历，返回成功与否。/将根节点入队，循环执行，出队，访问该节点，若该节点的左子节点不为空则将该节点的 左子节点入队，若该节点的右子节点不为空，则该节点的右子节点入队；直到队列为空。(4) 具体程序的实现#include#include#define TRUE 1#define FALSE 0
8、#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100/ 存储空间初始分配量#define STACKINCREMENT 10/ 存储空间分配增量typedef int Status; typedef int ElemType;/ Status是函数的类型，其值是函数结果状态代码，如OK等 /定义元素类型typedef struct BiTNode/生成树的结构体ElemType key;struct BiTNode *left,*right;左右孩子指针 BiTNode,*BiTree;BiTree InsertBiT(BiTree T,
9、ElemType key)BiTree f,p=T;/向树中写入数据，插入数据元素 keywhile(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;elseif(keykey)f-left=p;elsef-right=p;return T;BiTree CreateBiTree() BiTree T=NULL;ElemType key;/生成二叉树int n,i; scan
10、f(%d,&n); for(i=1;ikey); PreOrderTraverse(p-left); PreOrderTraverse(p-right);void InOrderTraverse(BiTree root)/中序遍历，递归算法BiTree p=root; if(p!=NULL)InOrderTraverse(p-left ); printf(%d ,p-key ); InOrderTraverse(p-right );void PostOrderTraverse(BiTree root)/后序遍历，递归算法BiTree p=root; if(p!=NULL)PostOrderTr
11、averse(p-left );PostOrderTraverse(p-right ); printf(%d ,p-key );Status visit(BiTree p) /输出结点的值printf(%d ,p-key); return OK;typedef BiTree SElemType;/预定义struct SqStack/建立栈的结构体SElemType *base; /在栈构造之前和销毁之后，base的值为NULLSElemType *top; / 栈顶指针int stacksize; / 当前已分配的存储空间，以元素为单位;Status InitStack(SqStack &S)
12、/构造一个空栈 SS.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status Push(SqStack &S,SElemType e)/插入元素 e 为新的栈顶元素if(S.top - S.base = S.stacksize )S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(
13、SElemType); if(!S.base)return ERROR;S.top = S.base + S.stacksize ;S.stacksize = S.stacksize + STACKINCREMENT;*S.top +=e;return OK;Status Pop(SqStack &S,SElemType &e)/弹出栈 S 的栈顶元素if(S.top =S.base )return ERROR;e=*-S.top ;return OK;Status StackEmpty(SqStack &S)/判断 S 是否是空栈，并返回值if(S.base=S.top)return TRUE;elsereturn FALSE;Status InOrderTraverseII(BiTree T) /二叉树的中序遍历算法(非递归算法) SqStack S; /利用栈来暂时
