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

《数据结构实验报告二叉排序树》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、WORD文档可编辑《数据结构》实验报告◎实验题目:创建一个二叉排序树，并以先序、中序、后序遍历输出。◎实验目的：熟练掌握二叉排序树建立的算法◎实验内容：已知n个元素，创建一个二叉排序树，以先序、中序、后序遍历输出，并计算每个节点的平衡因子。一、需求分析1.本程序输入应为一组数，将这组数作为关键字创建一个二叉排序树。2.本程序输出应为该建立好的二叉排序树的先序、中序、后序遍历输出，以及每个节点的平衡因子。3.程序执行的命令包括：（1）创建二叉排序树（2）先序非递归遍历输出（3）中序非递归遍历输出（4

2、）后序非递归遍历输出（5）计算并输出每个节点的平衡因子4.测试数据：输入元素的个数为8，元素为5325762048146084输出为：先序遍历：5325201448766084中序遍历：1420254853607684后序遍历：1420482560847653平衡因子：节点53的平衡因子为1节点25的平衡因子为1节点20的平衡因子为1节点14的平衡因子为0节点48的平衡因子为0节点76的平衡因子为0节点60的平衡因子为0节点84的平衡因子为0二概要设计为了实现以上操作，应以二叉链表为存储结构。1.

3、基本操作：node*create()创建二叉排序树voidNRPreorder(node*bt)先序非递归遍历输出voidNRinorder(node*bt)中序非递归遍历输出voidNRpostorder(node*bt)后序非递归遍历输出intheight(node*bt)计算左右子树深度voidshendu(node*bt)计算平衡因子2.本程序包含七个模块（1）主程序模块（2）二叉排序树创建模块技术资料专业分享WORD文档可编辑计算左右子树深度模块（1）先序遍历模块（2）中序遍历模块（3）

4、后序遍历模块（4）计算左右子树深度模块（5）计算平衡因子模块计算平衡因子模块1.模块调用图二叉排序树创建模块主程序模块后序遍历模块中序遍历模块先序遍历模块三详细设计 1．元素类型，结点类型和指针类型：#definemaxsize100typedefstructnode{chardata;structnode*lc;structnode*rc;}node;node*s[maxsize];node*bt;node*q,*p;2.每个模块的分析：（1）主程序模块：intmain(){node*bt;bt

5、=create();printf("该二叉树的先序递归遍历序列为:");preorder(bt);printf("");printf("该二叉树的中序递归遍历序列为:");inorder(bt);printf("");printf("该二叉树的后序递归遍历序列为:");技术资料专业分享WORD文档可编辑postorder(bt);printf("");printf("该二叉树的先序非递归遍历序列为:");NRPreorder(bt);printf("");printf("该二叉树的

6、中序非递归遍历序列为:");NRinorder(bt);printf("");printf("该二叉树的后序非递归遍历序列为:");NRpostorder(bt);printf("");printf("以先序遍历输出该二叉树，每个节点的平衡因子如下:");shendu(bt);getchar();getchar();return0;}（2）二叉排序树创建模块：node*create(){node*bt;node*q,*p;bt=NULL;/*根节点指针置空*/intx;inti;int

7、m;intj;printf("请输入数据个数:");scanf("%d",&m);printf("请输入数据:");for(j=0;jdata=x;q->lc=q->rc=NULL;if(bt==NULL)/*如果根节点指针为空，将其指向新申请节点*/bt=q;else{p=bt;/*活动指针指向根节点*/while(i

8、==0)技术资料专业分享WORD文档可编辑{if(p->data>x)/*如果新输入的数值比当前节点的数值小*/{if(p->lc!=NULL)/*如果当前节点的左孩子不为空，将活动指针移到它的左孩子*/p=p->lc;else/*否则将新申请节点链到当前节点的左孩子，将i标记为1，表示已处理*/{p->lc=q;i=1;}}else/*否则沿右链域比较*/{if(p->rc!=NULL)p=p->rc;else/*直到终端，插入输入节点*/{p->rc=q;i=1;}}}}}re