数据结构--6.5二叉排序树（插入，查找和删除）

目录

一、创建

 二、插入

三、删除

---

 

二叉排序树（Binary Sort Tree）又称为二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：

——若它的左子树不为空，则左子树上所有结点的值均小于它的根结构的值；

——若它的右子树不为空，则右子树上所有结点的值均大于它的根结构的值；

——它的左、右子树也分为二叉排序树（递归）。

一、创建

//二叉树的二叉链表结点结构定义
typedef struct BiTNOde
{int data;struct BiTNode * lchild,*rchild;
}BiTNode, *BiTree;//递归查找二叉排序树T中是否存在key
//指针f指向T的双亲，其初始值调用值为NULL
//若查找成功，则指针p指向该数据元素结点，并返回TRUE
//否则指针p指向查找路径上访问的最后一个结点，并返回FALSE
Status SearchBST(BiTree T,int key,BiTree f,BiTree *p)
{if(!T)   //查找不成功{*p = f;return FALSE; } else if(key == T->data){return SearchBST(T->lchild,key,T,p);    //在左子树继续查找 }else{return SearchBST(T->rchild,key,T,p);   //在右子树继续查找 } 
} 

 二、插入

//insertBST
//当二叉排序树T中不存在关键字等于key的数据元素时
Status InsertBST(BiTree *T,int key)
{BiTree p,s;if(!SearchBST(*T,key,NULL,&p)){s = (BiTree)malloc(sizeof(BiTNode));s->data = key;s->lchild = s->rchild = NULL;if(!p)		//查找不到key {*T = s; //插入s为新的根结点 }else if(key < p->data){p->lchild = s; //插入s为左孩子 } else {p->rchild = s; //插入s为右孩子 } return TURE; }else{return FALSE; //树中已有关键字相同的结点，不再插入 }} 

三、删除

Status DeleteBST(BiTree *T,int key)
{if(!*T){return FALSE;}else{if(key == (*T)->data){return Delete(T);}else if(key < (*T)->data){return DeleteBST(&(*T)->lchild,key);}else if(key > (*T)->data){return DeleteBST(&(*T)->rchild,key);}}} Status Delete(BiTree *p)
{BiTree q,s;if((*p)->rchild == NULL){p = *p;*p = (*p)->lchild;free(q);}else if((*p)->lchild == NULL){q = *p;*p = (*p)->rchild;free(q);}else{q = *p;s = (*p)->lchild;while(s->rchild){q = s;s = s->rchild;}(*p)->data = s->data;if(q  != p){q->rchild = s->lchild;}else{q->lchild = s->lchild;}free(s);}return tree;
}