C语言二叉排序树的创建,插入和删除

Irene ·

更新时间:2024-11-15

· 1987 次阅读

一、二叉排序树（二叉查找树）的概念

二、二叉排序树的判别

三、二叉排序树的创建（creat、insert）

四、二叉排序树的插入

五、二插排序树的删除

六、完整代码（可以运行）

总结

一、二叉排序树（二叉查找树）的概念

（1）若左子树非空，则左子树上所有结点的值均小于根节点的值

（2）若右子树非空，则右子树上所有结点的值均大于根节点的值

（3）左右子树分别也是一棵二叉排序树

tip：可以是一棵空树

二、二叉排序树的判别

（1）因为二叉排序树的中序遍历是一个有序递增序列，可以对已经建立的二叉树进行中序遍历，如果满足则判断是

三、二叉排序树的创建（creat、insert）

树结点的结构体：

struct tree{
int data;
struct tree* lchild;
struct tree* rchild;
};


//递归创建结点
void Creat(int a,tree* &T){
if(T==NULL){
T=new tree;
T->data=a;
T->lchild=NULL;
T->rchild=NULL;
}
else if(a>T->data){
Creat(a,T->rchild);
}
else{
Creat(a,T->lchild);
}
} 
//传入数组，一次性插入 
void Insert(tree* &T,int A[],int len){
for(int i=0;i<=len;i++){
Creat(A[i],T);
}
}

四、二叉排序树的插入


//查找指定结点(输出当前结点是否存在)，如果没有就插入 
void find(tree* &T,int a){
tree* K=T;     //T指针指向二叉排序树的根节点，K为工作指针 
tree* pre;   //pre指向当前工作指针的上一个结点，用于插入确定插入位置 
while(K!=NULL&&a!=K->data){
if(a>K->data){
pre=K;
K=K->rchild;
}else{
pre=K;
K=K->lchild;
}
}
if(K==NULL){
tree* P;    //工作指针
P=new tree;
P->data=a;
if(P->data>pre->data){
pre->rchild=P;
P->lchild=NULL;
P->rchild=NULL;
}
else{
    pre->lchild=P;
P->lchild=NULL;
P->rchild=NULL;
}
cout<<"不存在，已插入 "<<a<<" 这个结点"<<endl;
}else{
cout<<"存在"<<endl;
}
}

五、二插排序树的删除


//删除某一结点，若不存在则提示
//①当该结点是叶子结点时，直接删除
//②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置
//③当左右孩子都存在时找中序遍历的下一个(或上一个)结点代替其位置 
void delect(tree* &T,int a){
 //首先找到要删除的结点
 tree* Pre;
 tree* P=T;                      //定义工作指针 
 while(P!=NULL&&a!=P->data){     //这两个判定条件不能颠倒 
 if(a>P->data){
 Pre=P;
 P=P->rchild;
 }else{
 Pre=P;
 P=P->lchild;
 } 
} 
   if(P==NULL){
 cout<<"要删除的结点不存在"<<endl;
 }else{
 // ①当该结点是叶子结点时，直接删除
 if(P->lchild==NULL&&P->rchild==NULL){
 if(P->data>Pre->data){
 Pre->rchild=NULL;
 }else{
 Pre->lchild=NULL;
 }
 cout<<"已删除 "<<a<<endl; 
 }
 //②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置
 if((P->lchild!=NULL&&P->rchild==NULL)||(P->rchild!=NULL&&P->lchild==NULL)){
 if(P->data>Pre->data){
 if(P->lchild!=NULL){
 Pre->rchild=P->lchild;
 }else{
 Pre->rchild=P->rchild;
 }
 }
 if(P->data<Pre->data){
 if(P->lchild!=NULL){
 Pre->lchild=P->lchild;
 }else{
 Pre->lchild=P->rchild;
 }
 }
 cout<<"已删除 "<<a<<endl; 
 }
 //③当左右孩子都存在时找中序遍历的下一个（或上一个结点）结点代替其位置 (讨巧一点用前驱的最后一个结点)
 if(P->lchild!=NULL&&P->rchild!=NULL){
        tree* q;
        tree* s;
            q=P;
            s=P->lchild; 
    while(s->rchild)        //在结点p的左子树中继续查找其前驱结点,即最右下结点 
    {
           q=s;
   s=s->rchild;       //向右到尽头 
    }
 P->data=s->data;      //结点s中的数据顶替被删结点p中的 
    if(q!=P)              //重新连接结点q的右子树 
q->rchild=s->lchild;
else                    //重新连接结点q的左子树 
q->lchild=s->lchild;
delete(s);              //释放s 
  }
        cout<<"已删除 "<<a<<endl;
 } 
}

六、完整代码（可以运行）


#include<iostream>
using namespace std;
struct tree{
int data;
struct tree* lchild;
struct tree* rchild;
};
//建立创建，传入一个完整的数组 
void Creat(int a,tree* &T){
if(T==NULL){
T=new tree;
T->data=a;
T->lchild=NULL;
T->rchild=NULL;
}
else if(a>T->data){
Creat(a,T->rchild);
}
else{
Creat(a,T->lchild);
}
} 
//传入数组，一次性插入 
void Insert(tree* &T,int A[],int len){
for(int i=0;i<=len;i++){
Creat(A[i],T);
}
}
//中序遍历 
void midorder(tree* T){
if(T!=NULL){
    midorder(T->lchild);
cout<<T->data<<" ";
midorder(T->rchild);
}
}
//查找指定结点(输出当前结点是否存在)，如果没有就插入 
void find(tree* &T,int a){
tree* K=T;     //T指针指向二叉排序树的根节点，K为工作指针 
tree* pre;   //pre指向当前工作指针的上一个结点，用于插入确定插入位置 
while(K!=NULL&&a!=K->data){
if(a>K->data){
pre=K;
K=K->rchild;
}else{
pre=K;
K=K->lchild;
}
}
if(K==NULL){
tree* P;    //工作指针
P=new tree;
P->data=a;
if(P->data>pre->data){
pre->rchild=P;
P->lchild=NULL;
P->rchild=NULL;
}
else{
    pre->lchild=P;
P->lchild=NULL;
P->rchild=NULL;
}
cout<<"不存在，已插入 "<<a<<" 这个结点"<<endl;
}else{
cout<<"存在"<<endl;
}
}
//删除某一结点，若不存在则提示
//①当该结点是叶子结点时，直接删除
//②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置
//③当左右孩子都存在时找中序遍历的下一个(或上一个)结点代替其位置 
void delect(tree* &T,int a){
 //首先找到要删除的结点
 tree* Pre;
 tree* P=T;                      //定义工作指针 
 while(P!=NULL&&a!=P->data){     //这两个判定条件不能颠倒 
 if(a>P->data){
 Pre=P;
 P=P->rchild;
 }else{
 Pre=P;
 P=P->lchild;
 } 
} 
   if(P==NULL){
 cout<<"要删除的结点不存在"<<endl;
 }else{
 // ①当该结点是叶子结点时，直接删除
 if(P->lchild==NULL&&P->rchild==NULL){
 if(P->data>Pre->data){
 Pre->rchild=NULL;
 }else{
 Pre->lchild=NULL;
 }
 cout<<"已删除 "<<a<<endl; 
 }
 //②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置
 if((P->lchild!=NULL&&P->rchild==NULL)||(P->rchild!=NULL&&P->lchild==NULL)){
 if(P->data>Pre->data){
 if(P->lchild!=NULL){
 Pre->rchild=P->lchild;
 }else{
 Pre->rchild=P->rchild;
 }
 }
 if(P->data<Pre->data){
 if(P->lchild!=NULL){
 Pre->lchild=P->lchild;
 }else{
 Pre->lchild=P->rchild;
 }
 }
 cout<<"已删除 "<<a<<endl; 
 }
 //③当左右孩子都存在时找中序遍历的下一个（或上一个结点）结点代替其位置 (讨巧一点用前驱的最后一个结点)
 if(P->lchild!=NULL&&P->rchild!=NULL){
        tree* q;
        tree* s;
            q=P;
            s=P->lchild; 
    while(s->rchild)        //在结点p的左子树中继续查找其前驱结点,即最右下结点 
    {
           q=s;
   s=s->rchild;       //向右到尽头 
    }
 P->data=s->data;      //结点s中的数据顶替被删结点p中的 
    if(q!=P)              //重新连接结点q的右子树 
q->rchild=s->lchild;
else                    //重新连接结点q的左子树 
q->lchild=s->lchild;
delete(s);              //释放s 
  }
        cout<<"已删除 "<<a<<endl;
 } 
}
int main(){
tree* T=NULL;
int A[]={23,89,65,12,17,3,9,90,21,63,71};
Insert(T,A,10);
midorder(T);
delect(T,89);
midorder(T);
find(T,89);
midorder(T); 
return 0;
}