二叉搜索树使用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;
}