# 二进制搜索树删除操作

1. 没有孩子的节点（叶）
2. 有独生子女的节点
3. 有两个孩子的节点

## 代码

### 二进制搜索树删除操作的C ++代码

#include<bits/stdc++.h>
using namespace std;

struct node
{
int data;
node *left, *right;
};

node* create(int data){
node* tmp = new node();
tmp->data = data;
tmp->left = tmp->right = NULL;
}

void inorder(node* root){
if(root){
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}

// return the node which is in the most left direction of root
// the smallest node in the entire subtree rooted at current node
node* minNode(node* root)
{
node* tmp = root;
while(tmp && tmp->left)
tmp = tmp->left;
return tmp;
}

// deleted the node with given data from tree
node* deleteNode(node* root, int data)
{
// if current node is empty return current node(NULL)
if(!root) return root;

// node to be deleted is in left sub-tree
if (data < root->data)
root->left = deleteNode(root->left, data);
// node to be deleted in right sub-tree
else if (data > root->data)
root->right = deleteNode(root->right, data);
// current node is node to be deleted
else
{
// Case 1 + Case 2
// if left is null this means that it is either of the two cases
if (root->left == NULL)
{
node* tmp = root->right;
free(root);
return tmp;
}
// Case 2 node has a left child but not right child
// thus it has only a single child
else if (root->right == NULL)
{
node* tmp = root->left;
free(root);
return tmp;
}
// Case 3
// first find the successor
// successor is the element which comes next in inorder traversal of BST
// so it is the node in most left direction in right sub-tree
node *successor = minNode(root->right);
// place successor in place of current node
root->data = successor->data;
// now simply delete the successor from root's right child
root->right = deleteNode(root->right, successor->data);
}
return root;
}

int main()
{
node* root = create(7);
root->left = create(5);
root->right = create(8);
root->left->left = create(3);
root->left->left->right = create(4);
root->left->right = create(6);
cout<<"current inorder traversal of tree"<<endl;
inorder(root);
cout<<endl;
root = deleteNode(root, 5);
cout<<"inorder traversal after deleting node with value 5"<<endl;
inorder(root);
cout<<endl;
return 0;
}
current inorder traversal of tree
3 4 5 6 7 8
inorder traversal after deleting node with value 5
3 4 6 7 8

### 二进制搜索树删除操作的Java代码

import java.util.*;
// Class that denotes a node of the tree
class node
{
int data;
node left, right, random;

public node(int data)
{
this.data = data;
left = right = random = null;
}
}

class Tree
{
static node root;
static node create(int data) {
node tmp = new node(data);
return tmp;
}

static void inorder(node root){
if(root != null){
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}

// return the node which is in the most left direction of root
// the smallest node in the entire subtree rooted at current node
static node minNode(node root)
{
node tmp = root;
while(tmp != null && tmp.left != null)
tmp = tmp.left;
return tmp;
}

// deleted the node with given data from tree
static node deleteNode(node root, int data)
{
// if current node is empty return current node(NULL)
if(root == null) return root;
// node to be deleted is in left sub-tree
if (data < root.data)
root.left = deleteNode(root.left, data);
// node to be delted in right sub-tree
else if (data > root.data)
root.right = deleteNode(root.right, data);
// current node is node to be deleted
else
{
// Case 1 + Case 2
// if left is null this means that it is either of the two cases
if (root.left == null)
{
return root.right;
}
// Case 2 node has a left child but not right child
// thus it has only a single child
else if (root.right == null)
{
return root.left;
}
// Case 3
// first find the successor
// successor is the element which comes next in inorder traversal of BST
// so it is the node in most left direction in right sub-tree
node successor = minNode(root.right);
// place successor in place of current node
root.data = successor.data;
// now simply delete the successor from root's right child
root.right = deleteNode(root.right, successor.data);
}
return root;
}

public static void main(String[] args)
{
root = create(7);
root.left = create(5);
root.right = create(8);
root.left.left = create(3);
root.left.left.right = create(4);
root.left.right = create(6);
System.out.println("current inorder traversal of tree");
inorder(root);
System.out.println();
root = deleteNode(root, 5);
System.out.println("inorder traversal after deleting node with value 5");
inorder(root);
System.out.println();
}
}
current inorder traversal of tree
3 4 5 6 7 8
inorder traversal after deleting node with value 5
3 4 6 7 8

## 复杂度分析

### 空间复杂度

O（1）， 在删除操作期间。 我们没有存储任何信息，因此使算法占用恒定空间。