目录
1.二叉排序树概念
2.二叉排序树的插入
（1）二叉排序树的插入过程
（2）节点插入实现
3.二叉排序树的查找
4.二叉排序树的遍历
5.二叉树排序树节点的删除
（1）删除二叉排序树节点*P
6.完整的流程测试
使用C语言实现二叉树的链式存储
数据结构之折半查找（递归和非递归），插值查找和斐波那契查找
静态树表的查找（最优查找树和次优查找树）
二叉排序树（Binary Sort Tree）也称为二叉查找树后者二叉搜索树：
- 具有的性质：
- 1.若它的左子树不空，则左子树上的所有节点的值均小于它的根节点的值；
- 2.若它的右子树不空，则右子树上的所有节点的值均大于它的根节点的值；
- 3.若左右子树都不为空，左右子树也分别为二叉排序树；
二叉排序树结构的定义：
typedef int ElemType; typedef struct BSTNode{ ElemType data; struct BSTNode*lchild,*rchild; }*BSTree;
假设：现在有查找的关键字序列为{45,24,53,45,12,24,90}，二叉排序树的插入过程如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<stack>
void BSTreemenu(){
printf("---------------1.插入节点--------------\n");
printf("---------------2.查询节点--------------\n");
printf("---------------3.删除节点--------------\n");
printf("---------------4.输出节点--------------\n");
printf("---------------5.退出程序--------------\n");
}//构造一棵二叉排序树
int BST_Insert(BSTree&T,int key){
if(T==NULL){
T=(BSTree)malloc(sizeof(BSTNode));
T->data=key;
T->lchild=NULL;
T->rchild=NULL;
return 1;
}else if(T->data==key){
return 0;
}else if(T->data>key){
BST_Insert(T->lchild,key);
}else {
BST_Insert(T->rchild,key);
}
} 二叉排序树的查找过程类似于次优二叉树，查找步骤：
- 1.首先将给定值和根节点的值进行比较，若相等，则查找成功，否则进行第二步；
- 2.若给定的值大于根节点的值，则到根节点的右子树上进行相同的比较；
- 3.若给定的值小于根节点的值，则到根节点的左子树上进行相同的比较；
//递归查询节点
BSTNode*BST_Search(BSTree T,int key){
if(T==NULL)return NULL;
if(T->data==key){
return T;
}else if(T->data>key){
BST_Search(T->lchild,key);
}else{
BST_Search(T->rchild,key);
}
}
//非递归查询
BSTNode*BSTSearch(BSTree T,int key){
while(T!=NULL&&T->data!=key){
if(T->data>key){
T=T->lchild;
}else{
T=T->rchild;
}
}
} 该遍历和二叉树的遍历过程一样，但是这里有一个技巧，就是判断一棵二叉树是否为二叉排序树：如果中序遍历为有序的序列，则为二叉排序树。
//中序遍历二叉排序树(有序)
void BST_display(BSTree T){
if(T==NULL)return;
BST_display(T->lchild);
printf("%d ",T->data);
BST_display(T->rchild);
}
//删除节点操作
//情况一
void DeleteBSTOne(BSTree T,int key){
if(!T){
printf("不存在删除的节点!\n");
}else{
if(T->data==key){
free(T);
printf("删除成功!\n");
}else if(T->data>key){
DeleteBSTOne(T->lchild,key);
}else{
DeleteBSTOne(T->rchild,key);
}
}
}
//情况二,三
void DeleteBSTwoThree(BSTNode*p){
//如果*p不存在右子树，那么只需要将左子树挂到双亲上
BSTNode*q=NULL;
if(!p->rchild){
q=p;
p=p->lchild;
free(q);
}else if(!p->lchild){//否则接右子树
q=p;
p=p->rchild;
free(q);
}else{//左右子树都不空情况
q=p;
BSTNode*s=p->lchild;
//找到直接前驱，也就是*P左子树的最大值
while(s->rchild){
q=s;//q指向节点s的双亲
s=s->rchild;
}
p->data=s->data;
if(q!=p){
q->rchild=s->lchild;
}else{
q->lchild=s->lchild;
}
free(s);
}
printf("删除节点成功!");
return ;
}#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<stack>
typedef int ElemType;
typedef struct BSTNode{
ElemType data;
struct BSTNode*lchild,*rchild;
}*BSTree;
void BSTreemenu(){
printf("---------------1.插入节点--------------\n");
printf("---------------2.查询节点--------------\n");
printf("---------------3.删除节点--------------\n");
printf("---------------4.输出节点--------------\n");
printf("---------------5.退出程序--------------\n");
}
//构造一棵二叉排序树
int BST_Insert(BSTree&T,int key){
if(T==NULL){
T=(BSTree)malloc(sizeof(BSTNode));
T->data=key;
T->lchild=NULL;
T->rchild=NULL;
return 1;
}else if(T->data==key){
return 0;
}else if(T->data>key){
BST_Insert(T->lchild,key);
}else {
BST_Insert(T->rchild,key);
}
}
//销毁操作
void BST_Destroy(BSTree&T){
if(T==NULL)return ;
BST_Destroy(T->lchild);
BST_Destroy(T->rchild);
free(T);
}
//递归查询节点
BSTNode*BST_Search(BSTree T,int key){
if(T==NULL)return NULL;
if(T->data==key){
return T;
}else if(T->data>key){
BST_Search(T->lchild,key);
}else{
BST_Search(T->rchild,key);
}
}
//非递归查询
BSTNode*BSTSearch(BSTree T,int key){
while(T!=NULL&&T->data!=key){
if(T->data>key){
T=T->lchild;
}else{
T=T->rchild;
}
}
}
//中序遍历二叉排序树(有序)
void BST_display(BSTree T){
if(T==NULL)return;
BST_display(T->lchild);
printf("%d ",T->data);
BST_display(T->rchild);
}
//删除节点操作
//情况一
void DeleteBSTOne(BSTree T,int key){
if(!T){
printf("不存在删除的节点!\n");
}else{
if(T->data==key){
free(T);
printf("删除成功!\n");
}else if(T->data>key){
DeleteBSTOne(T->lchild,key);
}else{
DeleteBSTOne(T->rchild,key);
}
}
}
//情况二,三
void DeleteBSTwoThree(BSTNode*p){
//如果*p不存在右子树，那么只需要将左子树挂到双亲上
BSTNode*q=NULL;
if(!p->rchild){
q=p;
p=p->lchild;
free(q);
}else if(!p->lchild){//否则接右子树
q=p;
p=p->rchild;
free(q);
}else{//左右子树都不空情况
q=p;
BSTNode*s=p->lchild;
//找到直接前驱，也就是*P左子树的最大值
while(s->rchild){
q=s;//q指向节点s的双亲
s=s->rchild;
}
p->data=s->data;
if(q!=p){
q->rchild=s->lchild;
}else{
q->lchild=s->lchild;
}
free(s);
}
printf("删除节点成功!");
return ;
}
int main(){
BSTree T=NULL;
int key;
BSTNode*p;
int flag;
while(1){
int opt;
BSTreemenu();
printf("请输入操作: ");
scanf("%d",&opt);
switch(opt){
case 1:
printf("请输入元素(end=-1): ");
scanf("%d",&key);
while(key!=-1){
flag=BST_Insert(T,key);
if(flag==0){
printf("该元素已经存在\n");
}
printf("请输入元素(end=-1): ");
scanf("%d",&key);
}
break;
case 2:
printf("请输入要查找的元素: ");
scanf("%d",&key);
p=BST_Search(T,key);
if(p!=NULL){
printf("查找的元素为: %d\n",p->data);
}else{
printf("查找的元素不存在\n");
//不存在该元素，则插入
BST_Insert(T,key);
}
break;
case 3:
//这里删除节点只操作了叶子节点，关于有左子树（或者右子树），左右子树都不空情况代码已经实现，读者可以
//自己尝试
printf("请输入删除节点的值: ");
scanf("%d",&key);
DeleteBSTOne(T,key);
case 4:
BST_display(T);
printf("\n");
break;
default:
flag=5;
printf("退出操作:\n");
BST_Destroy(T);
break;
}
if(flag==5)break;
}
return 0;
}
