注 关于二叉搜索树更为详细的解释请详看 《大话数据结构》第八章 查找 中二叉搜索树这一小节
二叉排序树(Binary Sort Tree)，又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：
1，若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
2，若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值
3，它的左，右子树也分别为二叉排序树
- 二叉树排序树插入操作
简而言之就是将关键字放到树中的合适位置而已
// 往二叉排序树中插入数据
bitnode* InsertBST(bitnode *b, int m){
// 如果节点为空，则创建节点并返回
if(b == NULL){
b = (bitnode *)malloc(sizeof(bitnode));
b->data = m;
b->lchild = NULL;
b->rchild = NULL;
}
else{
// 如果插入数值小于节点数值
if(m < b->data){
b->lchild = InsertBST(b->lchild, m);
} // 如果插入数值大于节点数值
else if(m>b->data){
b->rchild = InsertBST(b->rchild, m);
}
else{ // 如果插入数值在二叉搜索树中已经存在则不会再次插入
cout<<endl<<m<<" 已经在二叉排序树中，无须再次插入!"<<endl;
}
}
return b;
}
- 二叉排序树创建操作
// 创建二叉排序树
bitnode* CreateBST(){
int len = 7;
int number[] = {5, 2, 7, 9, 15, 8, 3};
bitnode *head = NULL;
for(int i=0; i < len; i++){ //输入树的结点个数
head = InsertBST(head, number[i]);
}
return head;
}
- 二叉树排序树查找操作
// 在二叉排序树中查找是否有数值为 m 的节点
void searchBST(bitnode *b, int m){
if(b == NULL){
cout<<"查找失败"<<endl;
}
else{
if(m < b->data){
searchBST(b->lchild, m);
}
else if(m > b->data){
searchBST(b->rchild, m);
}
else{ // m == b->data
cout<<"查找成功!"<<endl;
}
}
}
- 二叉树排序树删除操作
删除操作欲删除节点分三种情况
1， 叶子节点
2，仅有左或右子树的节点
3，左右子树都有的节点
// 删除指定节点
bitnode* delteBST(bitnode *b, int m){
bitnode *q, *s;
if(b == NULL){
// 如果 b == NULL 则没查找到数据
cout<<"没有发现"<<endl;
}
else{
if(b->data == m){
if(b->lchild == NULL){ // 左孩子为空,只需要重接右子树
q = b;
b = b->rchild;
free(q);
}
else if(b->rchild == NULL){ // 右孩子为空，只需要重接左子树
q = b;
b = b->lchild;
free(q);
}
else{ // 左右孩子都不为空
q = b;
s = b->lchild;
while(s->rchild){
q = s;
s = s->rchild;
}
b->data = s->data;
if(q != b){
q->rchild = s->lchild;
}
else{
q->lchild = s->lchild;
}
free(s);
}
}
else if(m < b->data){
b->lchild = delteBST(b->lchild, m);
}
else if(m > b->data){
b->rchild = delteBST(b->rchild, m);
}
}
return b;
}
- 二叉树排序树总结
附完整代码
#include<iostream>
using namespace std;
typedef struct node{
int data; //节点信息
struct node *lchild; //左孩子
struct node *rchild; //右孩子
}bitnode;
// 往二叉排序树中插入数据
bitnode* InsertBST(bitnode *b, int m){
// 如果节点为空，则创建节点并返回
if(b == NULL){
b = (bitnode *)malloc(sizeof(bitnode));
b->data = m;
b->lchild = NULL;
b->rchild = NULL;
}
else{
// 如果插入数值小于节点数值
if(m < b->data){
b->lchild = InsertBST(b->lchild, m);
} // 如果插入数值大于节点数值
else if(m>b->data){
b->rchild = InsertBST(b->rchild, m);
}
else{ // 如果插入数值在二叉搜索树中已经存在则不会再次插入
cout<<endl<<m<<" 已经在二叉排序树中，无须再次插入!"<<endl;
}
}
return b;
}
// 创建二叉排序树
bitnode* CreateBST(){
int len = 7;
int number[] = {5, 2, 7, 9, 15, 8, 3};
bitnode *head = NULL;
for(int i=0; i < len; i++){ //输入树的结点个数
head = InsertBST(head, number[i]);
}
return head;
}
// 在二叉排序树中查找是否有数值为 m 的节点
void searchBST(bitnode *b, int m){
if(b == NULL){
cout<<"查找失败"<<endl;
}
else{
if(m < b->data){
searchBST(b->lchild, m);
}
else if(m > b->data){
searchBST(b->rchild, m);
}
else{ // m == b->data
cout<<"查找成功!"<<endl;
}
}
}
// 中序遍历，已验证插入或删除是否构成二叉排序树
// 如果是二叉排序树，则中序输出为递增
void zhongxu(bitnode *T){
if(T!=NULL){
zhongxu(T->lchild);
printf("%d ",T->data);
zhongxu(T->rchild);
}
}
// 删除指定节点
bitnode* delteBST(bitnode *b, int m){
bitnode *q, *s;
if(b == NULL){
// 如果 b == NULL 则没查找到数据
cout<<"没有发现"<<endl;
}
else{
if(b->data == m){
if(b->lchild == NULL){ // 左孩子为空,只需要重接右子树
q = b;
b = b->rchild;
free(q);
}
else if(b->rchild == NULL){ // 右孩子为空，只需要重接左子树
q = b;
b = b->lchild;
free(q);
}
else{ // 左右孩子都不为空
q = b;
s = b->lchild;
while(s->rchild){
q = s;
s = s->rchild;
}
b->data = s->data;
if(q != b){
q->rchild = s->lchild;
}
else{
q->lchild = s->lchild;
}
free(s);
}
}
else if(m < b->data){
b->lchild = delteBST(b->lchild, m);
}
else if(m > b->data){
b->rchild = delteBST(b->rchild, m);
}
}
return b;
}
int main(){
bitnode *head=NULL;
// 验证 CreateBST() 函数
head = CreateBST();
cout<<"创建二叉排序树: ";
zhongxu(head);
cout<<endl;
// 验证 InsertBST() 函数
head = InsertBST(head, 10);
head = InsertBST(head, 2);
cout<<endl<<"插入数值为 10, 2 的节点:";
zhongxu(head);
// 验证 delteBST() 函数
head = delteBST(head, 2);
cout<<endl<<"删除数值为 2 的节点: ";
zhongxu(head);
// 验证 searchBST() 函数
cout<<endl<<"搜索数值为 3 的节点: ";
searchBST(head, 3);
cout<<endl;
return 0;
}
网友评论