数据结构二叉排序树实验报告.docx
《数据结构二叉排序树实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构二叉排序树实验报告.docx（10页珍藏版）》请在冰点文库上搜索。
数据结构二叉排序树实验报告
实验报告
课程名：
数据结构（C语言版）
实验名：
二叉排序树
：
班级：
学号：
撰写时间：
2014.12.18
一实验目的与要求
1.掌握二叉排序树上进行插入和删除的操作
2.利用C语言实现该操作
二实验内容
•对于一个线形表,利用不断插入的方法,建立起一株二叉排序树
•从该二叉排序树中删除一个叶子节点,一个只有一个子树的非叶子节，一个有两个子树的非叶子节点。
三实验结果与分析
#include
#include
//二叉查找树结点描述
typedefintKeyType;
typedefstructNode
{
KeyTypekey;//关键字
structNode*left;//左孩子指针
structNode*right;//右孩子指针
structNode*parent;//指向父节点指针
}Node,*PNode;
//往二叉查找树中插入结点
//插入的话，可能要改变根结点的地址，所以传的是二级指针
voidinseart（PNode*root,KeyTypekey）
{
//初始化插入结点
PNodep=（PNode）malloc（sizeof（Node））;
p->key=key;
p->left=p->right=p->parent=NULL;
//空树时，直接作为根结点
if（（*root）==NULL）{
*root=p;
return;
}
//插入到当前结点（*root）的左孩子
if（（*root）->left==NULL&&（*root）->key>key）{
p->parent=（*root）;
（*root）->left=p;
return;
}
//插入到当前结点（*root）的右孩子
if（（*root）->right==NULL&&（*root）->keyp->parent=（*root）;
（*root）->right=p;
return;
}
if（（*root）->key>key）
inseart（&（*root）->left,key）;
elseif（（*root）->keyinseart（&（*root）->right,key）;
else
return;
}
//查找元素,找到返回关键字的结点指针，没找到返回NULL
PNodesearch（PNoderoot,KeyTypekey）
{
if（root==NULL）
returnNULL;
if（key>root->key）//查找右子树
returnsearch（root->right,key）;
elseif（keykey）//查找左子树
returnsearch（root->left,key）;
else
returnroot;
}
//查找最小关键字,空树时返回NULL
PNodesearchMin（PNoderoot）
{
if（root==NULL）
returnNULL;
if（root->left==NULL）
returnroot;
else//一直往左孩子找，直到没有左孩子的结点
returnsearchMin（root->left）;
}
//查找最大关键字,空树时返回NULL
PNodesearchMax（PNoderoot）
{
if（root==NULL）
returnNULL;
if（root->right==NULL）
returnroot;
else//一直往右孩子找，直到没有右孩子的结点
returnsearchMax（root->right）;
}
//查找某个结点的前驱
PNodesearchPredecessor（PNodep）
{
//空树
if（p==NULL）
returnp;
//有左子树、左子树中最大的那个
if（p->left）
returnsearchMax（p->left）;
//无左子树,查找某个结点的右子树遍历完了
else{
if（p->parent==NULL）
returnNULL;
//向上寻找前驱
while（p）{
if（p->parent->right==p）
break;
p=p->parent;
}
returnp->parent;
}
}
//查找某个结点的后继
PNodesearchSuccessor（PNodep）
{
//空树
if（p==NULL）
returnp;
//有右子树、右子树中最小的那个
if（p->right）
returnsearchMin（p->right）;
//无右子树,查找某个结点的左子树遍历完了
else{
if（p->parent==NULL）
returnNULL;
//向上寻找后继
while（p）{
if（p->parent->left==p）
break;
p=p->parent;
}
returnp->parent;
}
}
//根据关键字删除某个结点,删除成功返回1,否则返回0
//如果把根结点删掉，那么要改变根结点的地址，所以传二级指针
intdeleteNode（PNode*root,KeyTypekey）
{
PNodeq;
//查找到要删除的结点
PNodep=search（*root,key）;
KeyTypetemp;//暂存后继结点的值
//没查到此关键字
if（!
p）
return0;
//1.被删结点是叶子结点，直接删除
if（p->left==NULL&&p->right==NULL）{
//只有一个元素，删完之后变成一颗空树
if（p->parent==NULL）{
free（p）;
（*root）=NULL;
}else{
//删除的结点是父节点的左孩子
if（p->parent->left==p）
p->parent->left=NULL;
else//删除的结点是父节点的右孩子
p->parent->right=NULL;
free（p）;
}
}
//2.被删结点只有左子树
elseif（p->left&&!
（p->right））{
p->left->parent=p->parent;
//如果删除是父结点，要改变父节点指针
if（p->parent==NULL）
*root=p->left;
//删除的结点是父节点的左孩子
elseif（p->parent->left==p）
p->parent->left=p->left;
else//删除的结点是父节点的右孩子
p->parent->right=p->left;
free（p）;
}
//3.被删结点只有右孩子
elseif（p->right&&!
（p->left））{
p->right->parent=p->parent;
//如果删除是父结点，要改变父节点指针
if（p->parent==NULL）
*root=p->right;
//删除的结点是父节点的左孩子
elseif（p->parent->left==p）
p->parent->left=p->right;
else//删除的结点是父节点的右孩子
p->parent->right=p->right;
free（p）;
}
//4.被删除的结点既有左孩子，又有右孩子
//该结点的后继结点肯定无左子树（参考上面查找后继结点函数）
//删掉后继结点,后继结点的值代替该结点
else{
//找到要删除结点的后继
q=searchSuccessor（p）;
temp=q->key;
//删除后继结点
deleteNode（root,q->key）;
p->key=temp;
}
return1;
}
//创建一棵二叉查找树
voidcreate（PNode*root,KeyType*keyArray,intlength）
{
inti;
//逐个结点插入二叉树中
for（i=0;iinseart（root,keyArray[i]）;
}
intmain（void）
{
inti;
PNoderoot=NULL;
KeyTypenodeArray[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）;
return0;
}
图1：
二叉树排序实验结果
升级会员 