在本教程中，我们将看到如何从二进制搜索树中删除节点。

它有两部分。

• 搜索节点
• 在搜索该节点后，删除节点。

在从二进制搜索树中删除节点时，我们可能需要考虑三种情况。

• 如果节点有 no child
• 如果节点有 one child
• 如果节点有 two children。

如果节点没有孩子

这是非常直的案例。
我们需要搜索节点并使其null。

如果节点有一个孩子

如果节点有一个子项，那么我们需要将删除节点的父节点直接连接到删除节点的子节点。

如果节点有两个孩子

这是复杂的案例。
如果它有两个节点，我们需要将节点的父节点连接到右子树或者右侧的最右端树或者最右侧节点(最大值)。

让我们明白这种情况：

如我们所见，我们用节点50替换节点40.节点50是在移动之后在40和删除节点50的右子树中的最小元素，随后将重复节点。

为什么正确的子树的最小元素？

其中我们使用的是树可以以多种方式表示树的二进制搜索树属性。

例如：

我们正在使用相同的属性，同时删除有两个孩子的节点。

Java程序删除二进制搜索树中的节点

package org.igi.theitroad.binarysearchtree;
 
public class BinarySearchTreeDeleteMain {
	public static class TreeNode {
		int data;
		TreeNode left;
		TreeNode right;
 
		TreeNode(int data) {
			this.data = data;
		}
	}
 
	//Get minimum element in binary search tree
	public static TreeNode minimumElement(TreeNode root) {
		if (root.left == null)
			return root;
		else {
			return minimumElement(root.left);
		}
	}
 
	public static TreeNode deleteNode(TreeNode root, int value) {
		if (root == null)
			return null;
		if (root.data > value) {
			root.left = deleteNode(root.left, value);
		} else if (root.data < value) {
			root.right = deleteNode(root.right, value);
 
		} else {
			//if nodeToBeDeleted have both children
			if (root.left != null && root.right != null) {
				TreeNode temp = root;
				//Finding minimum element from right
				TreeNode minNodeForRight = minimumElement(temp.right);
				//Replacing current node with minimum node from right subtree
				root.data = minNodeForRight.data;
				//Deleting minimum node from right now
				root.right = deleteNode(root.right, minNodeForRight.data);
 
			}
			//if nodeToBeDeleted has only left child
			else if (root.left != null) {
				root = root.left;
			}
			//if nodeToBeDeleted has only right child
			else if (root.right != null) {
				root = root.right;
			}
			//if nodeToBeDeleted do not have child (Leaf node)
			else
				root = null;
		}
		return root;
	}
 
	public static TreeNode insert(TreeNode root, TreeNode nodeToBeInserted) {
		if (root == null) {
			root = nodeToBeInserted;
			return root;
		}
 
		if (root.data > nodeToBeInserted.data) {
			if (root.left == null)
				root.left = nodeToBeInserted;
			else
				insert(root.left, nodeToBeInserted);
		} else if (root.data < nodeToBeInserted.data)
			if (root.right == null)
				root.right = nodeToBeInserted;
			else
				insert(root.right, nodeToBeInserted);
		return root;
	}
 
	public static void inOrder(TreeNode root) {
		if (root == null)
			return;
		inOrder(root.left);
		System.out.print(root.data + " ");
		inOrder(root.right);
	}
 
	public static void main(String[] args) {
 
		//Creating a binary search tree
		TreeNode rootNode = createBinarySearchTree();
 
		System.out.println("Binary tree:");
		inOrder(rootNode);
		System.out.println();
		System.out.println("Deleting node 40 which have two children:");
		TreeNode rootNodeRes = deleteNode(rootNode, 40);
		inOrder(rootNodeRes);
	}
 
	public static TreeNode createBinarySearchTree() {
		TreeNode rootNode = new TreeNode(40);
		TreeNode node20 = new TreeNode(20);
		TreeNode node10 = new TreeNode(10);
		TreeNode node30 = new TreeNode(30);
		TreeNode node60 = new TreeNode(60);
		TreeNode node50 = new TreeNode(50);
		TreeNode node70 = new TreeNode(70);
		TreeNode node5 = new TreeNode(5);
		TreeNode node13 = new TreeNode(13);
		TreeNode node55 = new TreeNode(55);
 
		insert(null, rootNode);
		insert(rootNode, node20);
		insert(rootNode, node10);
		insert(rootNode, node30);
		insert(rootNode, node60);
		insert(rootNode, node50);
		insert(rootNode, node70);
		insert(rootNode, node5);
		insert(rootNode, node13);
		insert(rootNode, node55);
		return rootNode;
	}
}

运行上面的程序时，我们将获取以下输出：

Binary tree:
5 10 13 20 30 40 50 55 60 70 
Deleting node 40 which have two children:
5 10 13 20 30 50 55 60 70