C語言二叉排序樹的創(chuàng)建,插入和刪除
更新時間：2021年10月19日 08:49:15 作者：小哆-A
本文主要介紹了Java實(shí)現(xiàn)二叉排序樹的查找、插入、刪除、遍歷等內(nèi)容。具有很好的參考價值，下面跟著小編一起來看下吧
一、二叉排序樹（二叉查找樹）的概念
（1）若左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值
（2）若右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值
（3）左右子樹分別也是一棵二叉排序樹
tip：可以是一棵空樹
二、二叉排序樹的判別
（1）因?yàn)槎媾判驑涞闹行虮闅v是一個有序遞增序列，可以對已經(jīng)建立的二叉樹進(jìn)行中序遍歷，如果滿足則判斷是
三、二叉排序樹的創(chuàng)建（creat、insert）
樹結(jié)點(diǎn)的結(jié)構(gòu)體：
struct tree{
int data;
struct tree* lchild;
struct tree* rchild;
};
//遞歸創(chuàng)建結(jié)點(diǎn)
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);
}
}
//傳入數(shù)組，一次性插入
void Insert(tree* &T,int A[],int len){
for(int i=0;i<=len;i++){
Creat(A[i],T);
}
}
四、二叉排序樹的插入
//查找指定結(jié)點(diǎn)(輸出當(dāng)前結(jié)點(diǎn)是否存在)，如果沒有就插入
void find(tree* &T,int a){
tree* K=T; //T指針指向二叉排序樹的根節(jié)點(diǎn)，K為工作指針
tree* pre; //pre指向當(dāng)前工作指針的上一個結(jié)點(diǎn)，用于插入確定插入位置
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<<" 這個結(jié)點(diǎn)"<<endl;
}else{
cout<<"存在"<<endl;
}
}
五、二插排序樹的刪除
//刪除某一結(jié)點(diǎn)，若不存在則提示
//①當(dāng)該結(jié)點(diǎn)是葉子結(jié)點(diǎn)時，直接刪除
//②當(dāng)該結(jié)點(diǎn)有一個左孩子或者一個右孩子時，讓其孩子結(jié)點(diǎn)代替他的位置
//③當(dāng)左右孩子都存在時找中序遍歷的下一個(或上一個)結(jié)點(diǎn)代替其位置
void delect(tree* &T,int a){
//首先找到要刪除的結(jié)點(diǎn)
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<<"要刪除的結(jié)點(diǎn)不存在"<<endl;
}else{
// ①當(dāng)該結(jié)點(diǎn)是葉子結(jié)點(diǎn)時，直接刪除
if(P->lchild==NULL&&P->rchild==NULL){
if(P->data>Pre->data){
Pre->rchild=NULL;
}else{
Pre->lchild=NULL;
}
cout<<"已刪除 "<<a<<endl;
}
//②當(dāng)該結(jié)點(diǎn)有一個左孩子或者一個右孩子時，讓其孩子結(jié)點(diǎn)代替他的位置
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;
}
//③當(dāng)左右孩子都存在時找中序遍歷的下一個（或上一個結(jié)點(diǎn)）結(jié)點(diǎn)代替其位置 (討巧一點(diǎn)用前驅(qū)的最后一個結(jié)點(diǎn))
if(P->lchild!=NULL&&P->rchild!=NULL){
tree* q;
tree* s;
q=P;
s=P->lchild;
while(s->rchild) //在結(jié)點(diǎn)p的左子樹中繼續(xù)查找其前驅(qū)結(jié)點(diǎn),即最右下結(jié)點(diǎn)
{
q=s;
s=s->rchild; //向右到盡頭
}
P->data=s->data; //結(jié)點(diǎn)s中的數(shù)據(jù)頂替被刪結(jié)點(diǎn)p中的
if(q!=P) //重新連接結(jié)點(diǎn)q的右子樹
q->rchild=s->lchild;
else //重新連接結(jié)點(diǎn)q的左子樹
q->lchild=s->lchild;
delete(s); //釋放s
}
cout<<"已刪除 "<<a<<endl;
}
}
六、完整代碼（可以運(yùn)行）
#include<iostream>
using namespace std;
struct tree{
int data;
struct tree* lchild;
struct tree* rchild;
};
//建立創(chuàng)建，傳入一個完整的數(shù)組
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);
}
}
//傳入數(shù)組，一次性插入
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);
}
}
//查找指定結(jié)點(diǎn)(輸出當(dāng)前結(jié)點(diǎn)是否存在)，如果沒有就插入
void find(tree* &T,int a){
tree* K=T; //T指針指向二叉排序樹的根節(jié)點(diǎn)，K為工作指針
tree* pre; //pre指向當(dāng)前工作指針的上一個結(jié)點(diǎn)，用于插入確定插入位置
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<<" 這個結(jié)點(diǎn)"<<endl;
}else{
cout<<"存在"<<endl;
}
}
//刪除某一結(jié)點(diǎn)，若不存在則提示
//①當(dāng)該結(jié)點(diǎn)是葉子結(jié)點(diǎn)時，直接刪除
//②當(dāng)該結(jié)點(diǎn)有一個左孩子或者一個右孩子時，讓其孩子結(jié)點(diǎn)代替他的位置
//③當(dāng)左右孩子都存在時找中序遍歷的下一個(或上一個)結(jié)點(diǎn)代替其位置
void delect(tree* &T,int a){
//首先找到要刪除的結(jié)點(diǎn)
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<<"要刪除的結(jié)點(diǎn)不存在"<<endl;
}else{
// ①當(dāng)該結(jié)點(diǎn)是葉子結(jié)點(diǎn)時，直接刪除
if(P->lchild==NULL&&P->rchild==NULL){
if(P->data>Pre->data){
Pre->rchild=NULL;
}else{
Pre->lchild=NULL;
}
cout<<"已刪除 "<<a<<endl;
}
//②當(dāng)該結(jié)點(diǎn)有一個左孩子或者一個右孩子時，讓其孩子結(jié)點(diǎn)代替他的位置
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;
}
//③當(dāng)左右孩子都存在時找中序遍歷的下一個（或上一個結(jié)點(diǎn)）結(jié)點(diǎn)代替其位置 (討巧一點(diǎn)用前驅(qū)的最后一個結(jié)點(diǎn))
if(P->lchild!=NULL&&P->rchild!=NULL){
tree* q;
tree* s;
q=P;
s=P->lchild;
while(s->rchild) //在結(jié)點(diǎn)p的左子樹中繼續(xù)查找其前驅(qū)結(jié)點(diǎn),即最右下結(jié)點(diǎn)
{
q=s;
s=s->rchild; //向右到盡頭
}
P->data=s->data; //結(jié)點(diǎn)s中的數(shù)據(jù)頂替被刪結(jié)點(diǎn)p中的
if(q!=P) //重新連接結(jié)點(diǎn)q的右子樹
q->rchild=s->lchild;
else //重新連接結(jié)點(diǎn)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;
}
總結(jié)
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！
相關(guān)文章
這篇文章主要介紹了C語言的單鏈表、雙鏈表和循環(huán)鏈表，還有一些相關(guān)的實(shí)例，感興趣的同學(xué)可以借鑒一下2023-03-03
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)圖書館管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
QT已有項(xiàng)目導(dǎo)入工程時注意事項(xiàng)圖文詳解
QT開發(fā)這幾年大大小小項(xiàng)目做了不少,花了點(diǎn)時間對知識點(diǎn)總結(jié)整合了一部分,下面這篇文章主要給大家介紹了關(guān)于QT已有項(xiàng)目導(dǎo)入工程時注意事項(xiàng)的相關(guān)資料,需要的朋友可以參考下2023-11-11
這篇文章主要為大家詳細(xì)介紹了C語言銀行儲蓄系統(tǒng)源碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
C到C++的升級關(guān)系及區(qū)別實(shí)例探究
這篇文章主要為大家介紹了C到C++的升級關(guān)系及區(qū)別實(shí)例探究,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2024-01-01
這篇文章主要介紹了5分鐘內(nèi)了解C語言的指針,本文講解了指針、引用和取值、void指針、NULL指針和未初始化指針、指針和數(shù)組等內(nèi)容,需要的朋友可以參考下2015-01-01
這篇文章主要介紹了c語言沒有try catch的替代方案，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-06-06
這篇文章主要為大家詳細(xì)介紹了C語言代碼實(shí)現(xiàn)井字棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
C語言中實(shí)現(xiàn)“17進(jìn)制”轉(zhuǎn)“10進(jìn)制”實(shí)例代碼
這篇文章主要介紹了C語言中實(shí)現(xiàn)“17進(jìn)制”轉(zhuǎn)“10進(jìn)制”實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-05-05
本篇文章是對使用C++編寫無錯代碼的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05