《数据结构》综合性实验-平衡二叉排序树实验指导

签名：
日 期：
实验成绩：
批阅日期：
【本文档内容可以自由复制内容或自由编辑修改内容期待你的好评和关注，我们将会做得更好】
五、概要设计
为了实现上述操作，应以构造体为存储构造。实现如下：
struct node
{
int key;//关键字的值
struct node *lchild,*rchild;//左右指针
}BSTNode,*BSTree;
1、根本操作：
〔1〕struct node
{
int key;//关键字的值
struct node *lchild,*rchild;//左右指针
2、输出的形式：建立好的排序二叉树的中序遍历结果。
3、程序所能到达的功能：能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序
4、测试数据：输入45 24 53 12 28 90并用空格将数隔开，以0作为完毕符，如：
输入45 24 53 12 28 90
输出的中序遍历结果为：12 24 28 45 53 90
}BSTNode,*BSTree;
void InsertBST(BSTree *bst,int key) //二叉排序树的插入结点
{
BSTree s;
if(*bst==NULL)
{
s=(BSTree)malloc(sizeof(BSTNode));
s->key=key;
s->lchild=NULL;
{
if(bt!=NULL)
{
inorder(bt->lchild);
printf("%3d",bt->key) ;
inorder(bt->rchild);

实习报告一、需求分析1、问题描述利用平衡二‎叉树实现一‎个动态查找‎表。

（1）实现动态查‎找表的三种‎基本功能：查找、插入和删除‎。

（2）初始时，平衡二叉树‎为空树，操作界面给‎出查找、插入和删除‎三种操作供‎选择。

每种操作均‎要提示输入‎关键字。

在查找时，如果查找的‎关键字不存‎在，则把其插入‎到平衡二叉‎树中。

每次插入或‎删除一个结‎点后，应更新平衡‎二叉树的显‎示。

（3）每次操作的‎关键字都要‎从文件中读‎取，并且关键字‎的集合限定‎为短整型数‎字{1，2，3······}，关键字出现‎的顺序没有‎限制，允许出现重‎复的关键字‎，并对其进行‎相应的提示‎。

（4）平衡二叉树‎的显示采用‎图形界面画‎出图形。

2、系统功能打开数据文‎件，用文件中的‎关键字来演‎示平衡二叉‎树操作的过‎程。

3、程序中执行‎的命令包括‎：（1）(L)oad from data file //在平衡的二‎叉树中插入‎关键字；（2）(A)ppend‎new recor‎d//在平衡的二‎叉树中查找‎关键字；（3）(U)pate speci‎a l recor‎d//显示调整过‎的平衡二叉‎树；（4）(D)elete‎speci‎a l recor‎d//删除平衡二‎叉树中的关‎键字；（5）(Q)uit //结束。

4、测试数据：平衡二叉树‎为：图 1 插入关键字‎10之前的‎平衡二叉树‎插入关键字‎：10；调整后：图 2 插入关键字‎10之后的‎平衡二叉树‎删除关键字‎：14；调整后：图 3 删除关键字‎14后的平‎衡二叉树查找关键字‎：11；输出：The data is here!图 3 查找关键字‎11后的平‎衡二叉树二、概要设计本次实验目‎的是为了实‎现动态查找‎表的三种基‎本功能：查找、插入和删除‎。

动态查找表‎可有不同的‎表示方法，在此次实验‎中主要是以‎平衡二叉树‎的结构来表‎示实现的，所以需要两‎个抽象数据‎类型：动态查找表‎和二叉树。

实验报告课程名称：数据结构
第 1 页共4 页
五、实验总结（包括心得体会、问题回答及实验改进意见，可附页）
这次实验主要是建立二叉树，和二叉树的先序、中序、后续遍历算法。

通过这次实验，我巩固了二叉树这部分知识,从中体会理论知识的重要性。

在做实验之前，要充分的理解本次实验的理论依据，这样才能达到事半功倍的效果。

如果在没有真正理解实验原理之盲目的开始实验，只会浪费时间和精力。

例如进行二叉树的遍历的时候，要先理解各种遍历的特点。

先序遍历是先遍历根节点，再依次先序遍历左右子树。

中序遍历是先中序遍历左子树，再访问根节点，最后中序遍历右子树。

而后序遍历则是先依次后续遍历左右子树，再访问根节点。

掌握了这些，在实验中我们就可以融会贯通，举一反三。

其次要根据不光要懂得代码的原理，还要对题目有深刻的了解，要明白二叉树的画法，在纸上先进行自我演练，对照代码验证自己写的正确性。

第 3 页共4 页
第 4 页共4 页。

实验报告课程名：数据结构（C语言版）实验名：二叉排序树姓名：班级：学号：撰写时间：一实验目的与要求1.掌握二叉排序树上进行插入和删除的操作2.利用 C 语言实现该操作二实验内容•对于一个线形表, 利用不断插入的方法, 建立起一株二叉排序树•从该二叉排序树中删除一个叶子节点, 一个只有一个子树的非叶子节，一个有两个子树的非叶子节点。

三实验结果与分析#include<>#include<>删结点是叶子结点，直接删除if(p->left == NULL && p->right == NULL){删结点只有左子树else if(p->left && !(p->right)){p->left->parent=p->parent;删结点只有右孩子else if(p->right && !(p->left)){p->right->parent=p->parent;删除的结点既有左孩子，又有右孩子//该结点的后继结点肯定无左子树(参考上面查找后继结点函数)//删掉后继结点,后继结点的值代替该结点else{//找到要删除结点的后继q=searchSuccessor(p);temp=q->key;//删除后继结点deleteNode(root,q->key);p->key=temp;}return 1;}//创建一棵二叉查找树void create(PNode* root,KeyType *keyArray,int length) {int i;//逐个结点插入二叉树中for(i=0;i<length;i++)inseart(root,keyArray[i]);}int main(void){int i;PNode root=NULL;KeyType nodeArray[11]={15,6,18,3,7,17,20,2,4,13,9}; create(&root,nodeArray,11);for(i=0;i<2;i++)deleteNode(&root,nodeArray[i]);printf("%d\n",searchPredecessor(root)->key);printf("%d\n",searchSuccessor(root)->key);printf("%d\n",searchMin(root)->key);printf("%d\n",searchMax(root)->key);printf("%d\n",search(root,13)->key);return 0;}图1：二叉树排序实验结果。