# 二進制搜索樹刪除操作

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）， 在刪除操作期間。 我們沒有存儲任何信息，因此使算法佔用恆定空間。