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

《数据结构二叉排序树实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、/关键字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)==NU

3、LL){*root=p;return;}//插入到当前结点（*root）的左孩子if((*root)->left==NULL&&(*root)->key>key){p->parent=(*root);(*root)->left=p;return;}//插入到当前结点（*root）的右孩子if((*root)->right==NULL&&(*root)->keyparent=(*root);word资料.(*root)->right=p;return;}if((*root)->key>key)inseart(&(*root)->left,k

4、ey);elseif((*root)->keyright,key);elsereturn;}//查找元素,找到返回关键字的结点指针，没找到返回NULLPNodesearch(PNoderoot,KeyTypekey){if(root==NULL)returnNULL;if(key>root->key)//查找右子树returnsearch(root->right,key);elseif(keykey)//查找左子树returnsearch(root->left,key);elsereturnroo

5、t;}//查找最小关键字,空树时返回NULLPNodesearchMin(PNoderoot){if(root==NULL)returnNULL;if(root->left==NULL)returnroot;else//一直往左孩子找，直到没有左孩子的结点returnsearchMin(root->left);}//查找最大关键字,空树时返回NULLPNodesearchMax(PNoderoot){if(root==NULL)returnNULL;if(root->right==NULL)returnroot;else//一直往右孩子找，直到没有右孩子的

6、结点returnsearchMax(root->right);word资料.}//查找某个结点的前驱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->p

7、arent;}}//查找某个结点的后继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;}word资料.returnp->parent;}}//根据关键字删除某个结点,删除成

8、功返回1,否则返回0//如果把根结点删掉，那么要改变根结点的地址，