C語言二叉排序樹的創(chuàng)建,插入和刪除
更新時(shí)間：2021年10月19日 08:49:15 作者：小哆-A
本文主要介紹了Java實(shí)現(xiàn)二叉排序樹的查找、插入、刪除、遍歷等內(nèi)容。具有很好的參考價(jià)值，下面跟著小編一起來看下吧
一、二叉排序樹（二叉查找樹）的概念
（1）若左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值
（2）若右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值
（3）左右子樹分別也是一棵二叉排序樹
tip：可以是一棵空樹
二、二叉排序樹的判別
（1）因?yàn)槎媾判驑涞闹行虮闅v是一個(gè)有序遞增序列，可以對(duì)已經(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)前工作指針的上一個(gè)結(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<<" 這個(gè)結(jié)點(diǎn)"<<endl;
}else{
cout<<"存在"<<endl;
}
}
五、二插排序樹的刪除
//刪除某一結(jié)點(diǎn)，若不存在則提示
//①當(dāng)該結(jié)點(diǎn)是葉子結(jié)點(diǎn)時(shí)，直接刪除
//②當(dāng)該結(jié)點(diǎn)有一個(gè)左孩子或者一個(gè)右孩子時(shí)，讓其孩子結(jié)點(diǎn)代替他的位置
//③當(dāng)左右孩子都存在時(shí)找中序遍歷的下一個(gè)(或上一個(gè))結(jié)點(diǎn)代替其位置
void delect(tree* &T,int a){
//首先找到要?jiǎng)h除的結(jié)點(diǎn)
tree* Pre;
tree* P=T; //定義工作指針
while(P!=NULL&&a!=P->data){ //這兩個(gè)判定條件不能顛倒
if(a>P->data){
Pre=P;
P=P->rchild;
}else{
Pre=P;
P=P->lchild;
}
}
if(P==NULL){
cout<<"要?jiǎng)h除的結(jié)點(diǎn)不存在"<<endl;
}else{
// ①當(dāng)該結(jié)點(diǎn)是葉子結(jié)點(diǎn)時(shí)，直接刪除
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)有一個(gè)左孩子或者一個(gè)右孩子時(shí)，讓其孩子結(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)左右孩子都存在時(shí)找中序遍歷的下一個(gè)（或上一個(gè)結(jié)點(diǎn)）結(jié)點(diǎn)代替其位置 (討巧一點(diǎn)用前驅(qū)的最后一個(gè)結(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)建，傳入一個(gè)完整的數(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)前工作指針的上一個(gè)結(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<<" 這個(gè)結(jié)點(diǎn)"<<endl;
}else{
cout<<"存在"<<endl;
}
}
//刪除某一結(jié)點(diǎn)，若不存在則提示
//①當(dāng)該結(jié)點(diǎn)是葉子結(jié)點(diǎn)時(shí)，直接刪除
//②當(dāng)該結(jié)點(diǎn)有一個(gè)左孩子或者一個(gè)右孩子時(shí)，讓其孩子結(jié)點(diǎn)代替他的位置
//③當(dāng)左右孩子都存在時(shí)找中序遍歷的下一個(gè)(或上一個(gè))結(jié)點(diǎn)代替其位置
void delect(tree* &T,int a){
//首先找到要?jiǎng)h除的結(jié)點(diǎn)
tree* Pre;
tree* P=T; //定義工作指針
while(P!=NULL&&a!=P->data){ //這兩個(gè)判定條件不能顛倒
if(a>P->data){
Pre=P;
P=P->rchild;
}else{
Pre=P;
P=P->lchild;
}
}
if(P==NULL){
cout<<"要?jiǎng)h除的結(jié)點(diǎn)不存在"<<endl;
}else{
// ①當(dāng)該結(jié)點(diǎn)是葉子結(jié)點(diǎn)時(shí)，直接刪除
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)有一個(gè)左孩子或者一個(gè)右孩子時(shí)，讓其孩子結(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)左右孩子都存在時(shí)找中序遍歷的下一個(gè)（或上一個(gè)結(jié)點(diǎn)）結(jié)點(diǎn)代替其位置 (討巧一點(diǎn)用前驅(qū)的最后一個(gè)結(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)文章
今天小編就為大家分享一篇關(guān)于C++類的分離式寫法介紹示例，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2018-12-12
linux C++ 獲取文件絕對(duì)路徑的實(shí)例代碼
下面小編就為大家?guī)硪黄猯inux C++ 獲取文件絕對(duì)路徑的實(shí)例代碼。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-12-12
C/C++獲取當(dāng)前時(shí)間的方法總結(jié)(最全)
這篇文章主要為大家整理了C/C++中獲取當(dāng)前時(shí)間的最全方法，文中的示例代碼講解詳細(xì)，具有一定的學(xué)習(xí)和借鑒價(jià)值，需要的可以了解一下2023-03-03
C++實(shí)現(xiàn)正態(tài)隨機(jī)分布的方法
本篇介紹了，使用c++實(shí)現(xiàn)正態(tài)隨機(jī)分布的實(shí)現(xiàn)方法。需要的朋友參考下2013-05-05
這篇文章主要介紹了C語言實(shí)現(xiàn)推箱子游戲的代碼示例，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
C++輸出上三角/下三角/菱形/楊輝三角形(實(shí)現(xiàn)代碼)
本篇文章是對(duì)C++中輸出上三角/下三角/菱形/楊輝三角形的示例代碼進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-07-07
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-03-03
C語言動(dòng)態(tài)內(nèi)存的分配實(shí)例詳解
動(dòng)態(tài)內(nèi)存管理同時(shí)還具有一個(gè)優(yōu)點(diǎn),當(dāng)程序在具有更多內(nèi)存的系統(tǒng)上需要處理更多數(shù)據(jù)時(shí),不需要重寫程序,下面這篇文章主要給大家介紹了關(guān)于C語言動(dòng)態(tài)內(nèi)存分配的相關(guān)資料,需要的朋友可以參考下2022-06-06
這篇文章主要介紹了如何利用Matlab實(shí)現(xiàn)繪制有趣的羅盤時(shí)鐘，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Matlab有一定的幫助，需要的可以參考一下2023-01-01
C++示例分析內(nèi)聯(lián)函數(shù)與引用變量及函數(shù)重載的使用
為了消除函數(shù)調(diào)用的時(shí)空開銷，C++ 提供一種提高效率的方法，即在編譯時(shí)將函數(shù)調(diào)用處用函數(shù)體替換，類似于C語言中的宏展開。這種在函數(shù)調(diào)用處直接嵌入函數(shù)體的函數(shù)稱為內(nèi)聯(lián)函數(shù)（Inline Function），又稱內(nèi)嵌函數(shù)或者內(nèi)置函數(shù)2022-08-08