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

实验报告

课程名:数据结构（C语言版）

实验名：二叉排序树

姓名：

班级：

学号：

撰写时间:2023.12.18

一实验目的与规定

1.掌握二叉排序树上进行插入和删除的操作

2.运用C语言实现该操作

二实验内容

•对于一个线形表，运用不断插入的方法，建立起一株二叉排序树

•从该二叉排序树中删除一个叶子节点，一个只有一个子树的非叶子节，一

个有两个子树的非叶子节点。

三实验结果与分析

#include<stdio.h>

ttinclude<stdlib.h>

〃二叉查找树结点描述

typedefintKeyType；

typedefstructNode

{

KeyTypekey；//关键字

structNode*1eft;〃左孩子指针

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)->1eft==NULL&&(*root)->key>ke

y){

p->parent=(*root)；

(*root)->left=p;

return;

)

〃插入到当前结点(*root)的右孩子

if((*root)->right==NULL&&(*root)->key<key)

I

p->parent=(*root);

(*root)—>right=p;

return;

}

if((*root)->key>key)

inseart(&(*root)->left,key);

elseif((*root)->key<key)

inseart(&(*root)->right,key)；

e1se

return;

}

〃查找元素,找到返回关键字的结点指针,没找到返回NULL

PNodesearch(PNoderoot,KeyTypekey)

if(root==NULL)

returnNULL；

if(key>root->key)〃查找右子树

returnsearch(root->right,key);

elseif(key<root->key)//查找左子树

returnsearch(root—>left,key);

else

returnroot;

}

〃查找最小关键字,空树时返回NULL

PNodesearchMin(PNoderoot)

(

if(root==NULL)

returnNULL;

if(root->left==NULL)

returnroot;

else//一直往左孩子找，直到没有左孩子的结点

returnsearchMin(root->1eft);

)

〃查找最大关键字,空树时返回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->1eft);

//无左子树.，查找某个结点的右子树遍历完了

e1se{

if(p->parent==NULL)

returnNULL；

〃向上寻找前驱

whi1e(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;

//I.被删结点是叶子结点，直接删除

if(p->left==NULL&&p->right==NULL){

〃只有一个元素,删完之后变成一颗空树

if(p->parent==NULL){

free(p);

(*root)=NULL；

}else{

//删除的结点是父节点的左孩子

if(p->parent->left==p)

p->parent—>1eft=NULL;

else//删除的结点是父节点的右孩子

p->parent->right=NULL;

free(p);

}

)

//2.被删结点只有左子树

e1seif(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->1eft)){

p—>right—>parent=p->parent;

//假如删除是父结点,要改变父节点指针

if(p->parent==NULL)

*root=p->right;

//删除的结点是父节点的左孩子

elseif(p->parent->1eft==p)

p—>parent->left=p->right;

else〃删除的结点是父节点的右孩子

p->parent->right=p—>right;

free(p)；

)

//4.被删除的结点既有左孩子，又有右孩子

//该结点的后继结点肯定无左子树(参考上面查找后继结点函数)

〃删掉后继结点,后继结点的值代替该结点

e1se{

〃找到要删除结点的后继

q=searchSuccessor(p)；

temp=q->key;

//删除后继结点

deleteNode(root,q—>key);

p->key=temp;

)

return1;

//创建一棵二叉查找树

voidcreate(PNode*root,KeyType*keyArray,intlength)

inti;

//逐个结点插入二叉树中

for(i=0;i<length;i++)

inseart(root,keyArray[i])；

}

intmain(void)

(

inti;

PNoderoot=NULL;

KeyTypenodeArray[11]={