二叉排序树——练习

第1关：二叉排序树创建和插入

任务描述

本关任务：完成第一关代码，实现二叉排序树结点的查找、插入和创建操作。并完成中序遍历函数，通过输出结果验证二叉排序树是否正确创建。

相关知识

二叉排序树的创建是从空树开始，逐个插入的过程。 若二叉排序树中已经存在元素x，则无需插入元素x。 二叉排序树的查找算法，以下面的图为例说明：

第2关：在二叉排序树查找

任务描述

本关任务：在二叉排序树中查找查找最大值和最小值

第3关：二叉排序树的删除

任务描述

本关任务：完成函数，实现在二叉排序树中删除指定数据元素

通关代码：

#include 
#include 
//数据结构定义
struct node
{int data ;struct node *lchild ,*rchild ;
};typedef struct node *pTree;/*第一关*//*1.在二叉排序树T中查找指定数据元素element，若找到，返回1，且*p指向找到的结点；若未找到，返回0，且*p指向查找路径上的最后一个结点。*f只需查找路径上当前节点T的双亲。
*/
int findData(pTree T, pTree *f,pTree *p,int element)
{}/*2.创建一个二叉树结点,值为element*/ 
pTree createTreeNode(int element)
{pTree p=(pTree)malloc(sizeof(struct node));p->data=element;p->lchild=NULL;p->rchild=NULL;return p;}/*3.在二叉排序树中插入一个不存在的数据元素,若二叉树为空，则新建根节点*/
pTree insertData(int x , pTree T)
{if(T==NULL){T=createTreeNode(x);return T;}if(xdata){T->lchild=insertData(x,T->lchild);}if(x>T->data){T->rchild=insertData(x,T->rchild);}return T;
}/*4.中序遍历函数*/
void inOrder( pTree T)
{if(T==NULL){return;}inOrder(T->lchild);printf("%d ",T->data);inOrder(T->rchild);
}/*第二关*/
/*1.在二叉排序树T中查找最小值，返回该结点*/
pTree findMin(pTree T)
{if(!T){return NULL;}if(T){if(T->lchild) return findMin(T->lchild);return T;}}/*2.在二叉排序树T中查找最大值，返回该结点*/
pTree findMax(pTree T)
{if(!T){return NULL;}if(T){if(T->rchild) return findMax(T->rchild);return T;}}/*第三关*/
/*在二叉排序树T中删除指定元素的结点,
若删除成功则返回删除指定元素后的二叉排序树的根，
否则返回NULL
*/
int deleteData(pTree T,int element)
{pTree p,f,s,sq;p=f=T;while(p){if(element==p->data) break;else if(elementdata){f=p;p=p->lchild;}else{f=p;p=p->rchild;}}if(p==NULL){return NULL;}else{if(p->lchild==NULL && p->rchild==NULL){if(p->data==T->data){T->data=NULL;}else{if(p->datadata){f->lchild=NULL;}else{f->rchild=NULL;}free(p);}}else if(p->lchild!=NULL && p->rchild==NULL){if(p->data==T->data){f=T->lchild;T->data=f->data;T->lchild=f->lchild;free(f);}else{if(p->datadata){f->lchild=p->lchild;}else{f->rchild=p->lchild;}free(p);}}else if(p->lchild==NULL && p->rchild!=NULL){if(p->data==T->data){f=T->rchild;T->data=f->data;T->rchild=f->rchild;free(f);}else{if(p->datadata){f->lchild=p->rchild;}else{f->rchild=p->rchild;}free(p);}}else{sq=p;s=p->lchild;while(s->rchild!=NULL){sq=s;s=s->rchild;}if(s->lchild==NULL){sq->rchild=NULL;p->data=s->data;free(s);}else{if(sq->data==p->data){p->lchild=s->lchild;}else{sq->lchild=s->lchild;}p->data=s->data;free(s);}}}return T;}

有个findData方法没用到，后面更新。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！