2023年數(shù)據(jù)結(jié)構(gòu)二叉排序樹實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)報(bào)告

課程名:數(shù)據(jù)結(jié)構(gòu)（C語言版）

實(shí)驗(yàn)名：二叉排序樹

姓名：

班級(jí)：

學(xué)號(hào)：

撰寫時(shí)間:2023.12.18

一實(shí)驗(yàn)?zāi)康呐c規(guī)定

1.掌握二叉排序樹上進(jìn)行插入和刪除的操作

2.運(yùn)用C語言實(shí)現(xiàn)該操作

二實(shí)驗(yàn)內(nèi)容

?對(duì)于一個(gè)線形表，運(yùn)用不斷插入的方法，建立起一株二叉排序樹

?從該二叉排序樹中刪除一個(gè)葉子節(jié)點(diǎn)，一個(gè)只有一個(gè)子樹的非葉子節(jié)，一

個(gè)有兩個(gè)子樹的非葉子節(jié)點(diǎn)。

三實(shí)驗(yàn)結(jié)果與分析

#include<stdio.h>

ttinclude<stdlib.h>

〃二叉查找樹結(jié)點(diǎn)描述

typedefintKeyType；

typedefstructNode

{

KeyTypekey；//關(guān)鍵字

structNode*1eft;〃左孩子指針

structNode*right；//右孩子指針

structNode*parent；//指向父節(jié)點(diǎn)指針

}Node,*PNode；

//往二叉查找樹中插入結(jié)點(diǎn)

〃插入的話,也許要改變根結(jié)點(diǎn)的地址,所以傳的是二級(jí)指針

voidinseart(PNode*root,KeyTypekey)

//初始化插入結(jié)點(diǎn)

PNodep=(PNode)malloc(sizeof(Node));

p->key=key;

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

〃空樹時(shí)，直接作為根結(jié)點(diǎn)

if((root)==NULL){

*root=p;

return；

}

//插入到當(dāng)前結(jié)點(diǎn)(*root)的左孩子

if((*root)->1eft==NULL&&(*root)->key>ke

y){

p->parent=(*root)；

(*root)->left=p;

return;

)

〃插入到當(dāng)前結(jié)點(diǎn)(*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;

}

〃查找元素,找到返回關(guān)鍵字的結(jié)點(diǎn)指針,沒找到返回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;

}

〃查找最小關(guān)鍵字,空樹時(shí)返回NULL

PNodesearchMin(PNoderoot)

(

if(root==NULL)

returnNULL;

if(root->left==NULL)

returnroot;

else//一直往左孩子找，直到?jīng)]有左孩子的結(jié)點(diǎn)

returnsearchMin(root->1eft);

)

〃查找最大關(guān)鍵字,空樹時(shí)返回NULL

PNodesearchMax(PNoderoot)

{

if(root==NULL)

returnNULL;

if(root->right==NULL)

returnroot；

else〃一直往右孩子找，直到?jīng)]有右孩子的結(jié)點(diǎn)

returnsearchMax(root->right);

}

〃查找某個(gè)結(jié)點(diǎn)的前驅(qū)

PNodesearchPredecessor(PNodep)

(

//空樹

if(p==NULL)

returnp;

//有左子樹、左子樹中最大的那個(gè)

if(p->left)

returnsearchMax(p->1eft);

//無左子樹.，查找某個(gè)結(jié)點(diǎn)的右子樹遍歷完了

e1se{

if(p->parent==NULL)

returnNULL；

〃向上尋找前驅(qū)

whi1e(p){

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

break;

p=p->parent；

)

returnp->parent;

)

卜

//查找某個(gè)結(jié)點(diǎn)的后繼

PNodesearchSuccessor(PNodep)

(

〃空樹

if(p==NULL)

returnp;

//有右子樹、右子樹中最小的那個(gè)

if(p->right)

returnsearchMin(p->right);

//無右子樹,查找某個(gè)結(jié)點(diǎn)的左子樹遍歷完了

else{

if(p—>parent==NULL)

returnNULL；

//向上尋找后繼

while(p){

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

break;

p=p->parent;

}

returnp->parent;

)

)

〃根據(jù)關(guān)鍵字刪除某個(gè)結(jié)點(diǎn)，刪除成功返回1,否則返回0

//假如把根結(jié)點(diǎn)刪掉，那么要改變根結(jié)點(diǎn)的地址,所以傳二級(jí)指針

intdeleteNode(PNode*root,KeyTypekey)

(

PNodeq；

//查找到要?jiǎng)h除的結(jié)點(diǎn)

PNodep=search(*root,key);

KeyTypetemp;//暫存后繼結(jié)點(diǎn)的值

〃沒查到此關(guān)鍵字

if(!p)

return0;

//I.被刪結(jié)點(diǎn)是葉子結(jié)點(diǎn)，直接刪除

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

〃只有一個(gè)元素,刪完之后變成一顆空樹

if(p->parent==NULL){

free(p);

(*root)=NULL；

}else{

//刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子

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

p->parent—>1eft=NULL;

else//刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子

p->parent->right=NULL;

free(p);

}

)

//2.被刪結(jié)點(diǎn)只有左子樹

e1seif(p->left&&!(p—>right)){

p->left—>parent=p->parent；

//假如刪除是父結(jié)點(diǎn)，要改變父節(jié)點(diǎn)指針

if(p->parent==NULL)

*root=p->left；

〃刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子

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

p->parent->left=p->left;

else〃刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子

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

free(p);

)

//3.被刪結(jié)點(diǎn)只有右孩子

elseif(p->right&&!(p->1eft)){

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

//假如刪除是父結(jié)點(diǎn),要改變父節(jié)點(diǎn)指針

if(p->parent==NULL)

*root=p->right;

//刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子

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

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

else〃刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子

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

free(p)；

)

//4.被刪除的結(jié)點(diǎn)既有左孩子，又有右孩子

//該結(jié)點(diǎn)的后繼結(jié)點(diǎn)肯定無左子樹(參考上面查找后繼結(jié)點(diǎn)函數(shù))

〃刪掉后繼結(jié)點(diǎn),后繼結(jié)點(diǎn)的值代替該結(jié)點(diǎn)

e1se{

〃找到要?jiǎng)h除結(jié)點(diǎn)的后繼

q=searchSuccessor(p)；

temp=q->key;

//刪除后繼結(jié)點(diǎn)

deleteNode(root,q—>key);

p->key=temp;

)

return1;

//創(chuàng)建一棵二叉查找樹

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

inti;

//逐個(gè)結(jié)點(diǎn)插入二叉樹中

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

inseart(root,keyArray[i])；

}

intmain(void)

(

inti;

PNoderoot=NULL;

KeyTypenodeArray[11]={