数据结构实验报告二叉排序树.docVIP

WORD格式整理 专业知识分享 《数据结构》实验报告 ◎实验题目: 创建一个二叉排序树，并以先序、中序、后序遍历输出。 ◎实验目的：熟练掌握二叉排序树建立的算法 ◎实验内容：已知n个元素，创建一个二叉排序树，以先序、中序、后序遍历输出， 并计算每个节点的平衡因子。 一、需求分析 1.本程序输入应为一组数，将这组数作为关键字创建一个二叉排序树。 2.本程序输出应为该建立好的二叉排序树的先序、中序、后序遍历输出，以及每个节点的平衡因子。 3. 程序执行的命令包括：（1）创建二叉排序树（2）先序非递归遍历输出（3）中序非递归遍历输出（4）后序非递归遍历输出（5）计算并输出每个节点的平衡因子 4.测试数据： 输入元素的个数为8，元素为53 25 76 20 48 14 60 84 输出为： 先序遍历：53 25 20 14 48 76 60 84 中序遍历：14 20 25 48 53 60 76 84 后序遍历：14 20 48 25 60 84 76 53 平衡因子：节点53的平衡因子为1 节点25的平衡因子为1 节点20的平衡因子为1 节点14的平衡因子为0 节点48的平衡因子为0 节点76的平衡因子为0 节点60的平衡因子为0 节点84的平衡因子为0 二 概要设计 为了实现以上操作，应以二叉链表为存储结构。 基本操作： node *create() 创建二叉排序树 void NRPreorder(node *bt) 先序非递归遍历输出 void NRinorder(node *bt) 中序非递归遍历输出 void NRpostorder(node *bt) 后序非递归遍历输出 int height(node *bt) 计算左右子树深度 void shendu(node *bt) 计算平衡因子 本程序包含七个模块 主程序模块 二叉排序树创建模块 计算左右子树深度模块先序遍历模块 计算左右子树深度模块 中序遍历模块 后序遍历模块 计算左右子树深度模块 计算平衡因子模块 计算平衡因子模块模块调用图 计算平衡因子模块 二叉排序树创建模块 二叉排序树创建模块 主程序模块 主程序模块 后序遍历模块中序遍历模块先序遍历模块 后序遍历模块 中序遍历模块 先序遍历模块 三 详细设计? 元素类型，结点类型和指针类型： #define maxsize 100 typedef struct node { char data; struct node *lc; struct node *rc; }node; node *s[maxsize]; node *bt; node *q,*p; 2.每个模块的分析： （1）主程序模块： int main() { node *bt; bt=create(); printf(该二叉树的先序递归遍历序列为: ); preorder(bt); printf(\n); printf(该二叉树的中序递归遍历序列为: ); inorder(bt); printf(\n); printf(该二叉树的后序递归遍历序列为: ); postorder(bt); printf(\n); printf(该二叉树的先序非递归遍历序列为:); NRPreorder(bt); printf(\n); printf(该二叉树的中序非递归遍历序列为:); NRinorder(bt); printf(\n); printf(该二叉树的后序非递归遍历序列为:); NRpostorder(bt); printf(\n); printf(以先序遍历输出该二叉树，每个节点的平衡因子如下:\n); shendu(bt); getchar(); getchar(); return 0; } （2）二叉排序树创建模块： node *create() { node *bt; node *q,*p; bt=NULL; /*根节点指针置空*/ int x; int i; int m; int j; printf(请输入数据个数:\n); scanf(%d,m); printf(请输入数据:\n); for(j=0;jm;j++) { scanf(%d,x); i=0; q=(node *)malloc(sizeof(node)); /*申请新节点，将新节点数据