C語言二叉排序樹的創(chuàng)建,插入和刪除
更新時間：2021年10月19日 08:49:15 作者：小哆-A
本文主要介紹了Java實現(xiàn)二叉排序樹的查找、插入、刪除、遍歷等內(nèi)容。具有很好的參考價值，下面跟著小編一起來看下吧
一、二叉排序樹（二叉查找樹）的概念
（1）若左子樹非空，則左子樹上所有結點的值均小于根節(jié)點的值
（2）若右子樹非空，則右子樹上所有結點的值均大于根節(jié)點的值
（3）左右子樹分別也是一棵二叉排序樹
tip：可以是一棵空樹
二、二叉排序樹的判別
（1）因為二叉排序樹的中序遍歷是一個有序遞增序列，可以對已經(jīng)建立的二叉樹進行中序遍歷，如果滿足則判斷是
三、二叉排序樹的創(chuàng)建（creat、insert）
樹結點的結構體：
struct tree{
int data;
struct tree* lchild;
struct tree* rchild;
};
//遞歸創(chuàng)建結點
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 find(tree* &T,int a){
tree* K=T; //T指針指向二叉排序樹的根節(jié)點，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的左子樹中繼續(xù)查找其前驅結點,即最右下結點
{
q=s;
s=s->rchild; //向右到盡頭
}
P->data=s->data; //結點s中的數(shù)據(jù)頂替被刪結點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;
};
//建立創(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);
}
}
//查找指定結點(輸出當前結點是否存在)，如果沒有就插入
void find(tree* &T,int a){
tree* K=T; //T指針指向二叉排序樹的根節(jié)點，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的左子樹中繼續(xù)查找其前驅結點,即最右下結點
{
q=s;
s=s->rchild; //向右到盡頭
}
P->data=s->data; //結點s中的數(shù)據(jù)頂替被刪結點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;
}
總結
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關注腳本之家的更多內(nèi)容！
相關文章
今天小編就為大家分享一篇關于C++類的分離式寫法介紹示例，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
下面小編就為大家?guī)硪黄猯inux C++ 獲取文件絕對路徑的實例代碼。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
這篇文章主要為大家整理了C/C++中獲取當前時間的最全方法，文中的示例代碼講解詳細，具有一定的學習和借鑒價值，需要的可以了解一下2023-03-03
本篇介紹了，使用c++實現(xiàn)正態(tài)隨機分布的實現(xiàn)方法。需要的朋友參考下2013-05-05
這篇文章主要介紹了C語言實現(xiàn)推箱子游戲的代碼示例，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-09-09
C++輸出上三角/下三角/菱形/楊輝三角形(實現(xiàn)代碼)
本篇文章是對C++中輸出上三角/下三角/菱形/楊輝三角形的示例代碼進行了詳細的分析介紹，需要的朋友參考下2013-07-07
這篇文章主要為大家詳細介紹了C++實現(xiàn)掃雷游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
動態(tài)內(nèi)存管理同時還具有一個優(yōu)點,當程序在具有更多內(nèi)存的系統(tǒng)上需要處理更多數(shù)據(jù)時,不需要重寫程序,下面這篇文章主要給大家介紹了關于C語言動態(tài)內(nèi)存分配的相關資料,需要的朋友可以參考下2022-06-06
這篇文章主要介紹了如何利用Matlab實現(xiàn)繪制有趣的羅盤時鐘，文中的示例代碼講解詳細，對我們學習Matlab有一定的幫助，需要的可以參考一下2023-01-01
C++示例分析內(nèi)聯(lián)函數(shù)與引用變量及函數(shù)重載的使用
為了消除函數(shù)調(diào)用的時空開銷，C++ 提供一種提高效率的方法，即在編譯時將函數(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