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

实验报告课程名:数据结构（C语言版）实验名：二叉排序树姓名：班级：学号：撰写时间：2023.12.18inti;//逐个结点插入二叉树中for(i=0;i<length;i++)inseart(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(，z%d\n〃，searchPredecessor(root)->key)；printfsearchSuccessor(root)->key);printf(%d\n〃，searchMin(root)—>key);printf("%d\nn,searchMax(root)->key)；printf(〃％d\n〃，search(root,13)->key);return0；,■C:\Users\Administrator\DesktopVS据结的---\Debug\二叉树排序.exe"131822013Pressanykeytocontinue图1:二义树排序实验结果一实验目的与规定.掌握二叉排序树上进行插入和删除的操作.运用C语言实现该操作二实验内容•对于一个线形表，运用不断插入的方法，建立起一株二叉排序树•从该二叉排序树中删除一个叶子节点，一个只有一个子树的非叶子节，一个有两个子树的非叶子节点。三实验结果与分析#include<stdio.h>#include<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>key){p->parent=(*root)；(*root)->left=p;return;}〃插入到当前结点(*root)的右孩子if((*root)->right==NULL&&(*root)->key<key)(p—>parent=(*root);(*root)—>right=p;return;}if((*root)->key>key)inseart(&(*root)->left,key);elseif((*root)->key<key)

inseart(&(*root)->right,key)；e1sereturn;}〃查找元素,找到返回关键字的结点指针,没找到返回NULLPNodesearch(PNoderoot,KeyTypekey)(if(root==NULL)returnNULL；if(key>root->key)〃查找右子树returnsearch(root->right,key);elseif(key<root->key)//查找左子树returnsearch(root—>left,key);elsereturnroot;}〃查找最小关键字,空树时返回NULLPNodesearchMin(PNoderoot)(if(root==NULL)returnNULL;if(root->left==NULL)returnroot;else//一直往左孩子找，直到没有左孩子的结点returnsearchMin(root->1eft);〃查找最大关键字,空树时返回NULLPNodesearchMax(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;}I//查找某个结点的后继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(1p)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—>parcnt=p->parent;//假如删除是父结点,要改变父节点指针if(p->parent==NULL)*root=p->right;//删除的结点是父节点的左孩子elseif(p->parent->1eft==p)

p—>parent->left=p->right;eIse〃删除的结点是父节点的右孩子p->paront->right=p—>right;free(p)；}//4.被删除的结点既有左孩子,又有右孩子//该结点的后继结点肯定无左子树(参考上面查找后继结点函数)〃删掉后继