二叉搜索樹使用c++語言如何實現刪除節點的操作

在之前的經驗傍邊，我已經介紹了二叉搜刮樹的插入與搜刮的操作。因為刪除節點的操作，比擬較于搜刮與插入的操作，略顯復雜，需要針對節點的子節點個數進行會商。是以，本章特意會商了二叉搜刮樹的刪除操作。

東西/原料

code::blocks
c++ 11編譯器

方式/步調

1
第一步簡單介紹一下什么是二叉搜刮樹（Binary Search Tree）。二叉搜刮樹是二叉樹的一種，一個節點最多只有兩個子節點，可是節點的左子節點的值要小于節點的值，節點右子節點的值要年夜于節點的值。
2
刪除操作需要針對子節點個數進行會商。
1、若是一個節點的子節點個數為0，就可以直接刪除這個節點
3
2、若是這個節點的子節點個數是一個，那么就需要再刪除該節點之后，將該節點的子節點和父節點毗連到一路。
4
3、若是該節點的子節點個數為兩個，那么這個環境比力復雜。這個時辰需要在該節點的右子樹中找到最小的節點來替代該節點。這一步的操作需要經由過程遞歸來實現。具體代碼看下一步。
5
光說不做不可，這一步我們將展示上述三步的具體代碼實現過程。下圖所供給的代碼是一個類的方式。僅供參考。
6
為了整個法式的完整性，這一步調，我們供給整個二叉搜刮樹的實現代碼，包羅搜刮、插入、刪除、尋找最年夜最小值。如下:
#include <iostream>
using namespace std;
//tree node
struct node
{
int key;
struct node *left,*right;
};
//construct new node
struct node* newnode(int item)
{
struct node* temp=new node;
temp->key=item;
temp->left=nullptr;
temp->right=nullptr;
return temp;
};
//inorder travel
void inorder(struct node* root)
{
if (root!=nullptr)
{
inorder(root->left);
cout<<root->key<<endl;
inorder(root->right);
}
}
class BinarySearchTree
{
public:
BinarySearchTree(){root=nullptr;};
//find the minimum value
struct node *findmin(struct node*t)
{
if (t==nullptr)
return nullptr;
if (t->left==nullptr)
return t;
else
findmin(t->left);
};
//find a maximum value
struct node*findmax(struct node*t)
{
if (t==nullptr)
return nullptr;
if (t->right==nullptr)
return t;
else
findmax(t->right);
};
//if a node in Binary search tree
bool contains(struct node* t,int item)
{
if (t==nullptr)
return false;
else if (item>t->key)
contains(t->right,item);
else if (item<t->key)
contains(t->left,item);
else
return true;
}
//delete a node
struct node* deleteNode(struct node* t,int item)
{
if (t==nullptr)
return t;
if (item<t->key)
t->left=deleteNode(t->left,item);
else if (item>t->key)
t->right=deleteNode(t->right,item);
else
{
if (t->left==nullptr)
{
struct node *temp=t->right;
delete t;
return temp;
}
else if (t->right==nullptr)
{
struct node*temp=t->left;delete t;
return temp;
}
struct node* temp=findmin(t->right);
t->key=temp->key;
t->right=deleteNode(t->right,temp->key);
}
return t;
};
//insert a node
struct node* insert(struct node* t,int item)
{
if (t==nullptr&&root==nullptr)
{
root=newnode(item);
return root;
}
if (t==nullptr &&root!=nullptr)
return newnode(item);
if (item<t->key)
t->left=insert(t->left,item);
if (item>t->key)
t->right=insert(t->right,item);
root=t;
return root;
}
struct node* root;
};
int main()
{
BinarySearchTree tr;
tr.insert(tr.root,60);
tr.insert(tr.root,10);
tr.insert(tr.root,20);
tr.insert(tr.root,30);
tr.insert(tr.root,500);
tr.insert(tr.root,40);
cout<<"inorder travel "<<endl;
inorder(tr.root);
cout<<"if contains 10: "<<endl;
cout<<tr.contains(tr.root,10)<<endl;
cout<<"findmin "<<tr.findmin(tr.root)->key<<endl;
cout<<"delete 40 "<<endl;
tr.deleteNode(tr.root,40);
inorder(tr.root);
return 0;
}