PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接

目录

1、二叉树的删除

 1、1 根节点的删除 1、2 非叶子节点（该节点含有子节点但该节点又不是根节点）的删除 1、3 叶子节点的删除

1、二叉树的删除

说二叉树的删除之前，咱们先给本人的二叉树定义一些规定：左子节点的值小于等于父节点的值，右子节点的值大于父节点的值，也就是说进行这棵二叉树的中序遍历是升序的；对于二叉树的中序遍历，如果不懂的话，能够看Java版的数据结构和算法（四）这篇文章；二叉树的删除可分为3种状况，它们是根节点的删除、非叶子节点（该节点含有子节点但该节点又不是根节点）的删除和叶子节点的删除，上面咱们对它们一个一个的进行剖析。

1、1 根节点的删除

以根节点造成一棵二叉树时分为4种状况：根节点没有子节点、根节点只有左子树、根节点只有右子树和根节点左右子树都有。

1）根节点没有子节点而进行删除根节点的思路：

（1）间接将根节点置空即可。

2）根节点只有左子树而进行删除根节点的思路：

（1）间接将根节点指向根节点的左子树。

3）根节点只有右子树而进行删除根节点的思路：

（1）间接将根节点指向根节点的右子树。

4）根节点左右子树都有而进行删除根节点的思路：

（1）先拿到根节点的左右2棵子树，用根节点指向右子树，这样就实现了删除根节点。

（2）这样就造成了2棵二叉树，咱们还得把2棵二叉树组合成一棵二叉树，因为旧的根节点的右子节点的值肯定是大于旧的根节点的左子节点的值，这个不必狐疑的，因为后面咱们曾经制订了二叉树的一些规定，所以旧的根节点的右子节点就会成为新的根节点。

（3）旧的根节点的左子节点肯定是挂在新的根节点的子节点或者子子节点之中，顺次类推是成为谁的子节点，一开始假设新的根节点行将成为旧的根节点的左子节点的 “父节点”。

（4）如果旧的根节点的左子节点的值小于等于 “父节点” 的值并且 “父节点” 的左子节点为空，那么就将旧的根节点的左子节点设置为 “父节点” 的左子节点，实现2棵二叉树的组合，这时候 “父节点” 就真的是 旧的根节点的左子节点的父节点，那么就不用走（5-7）的步骤。

（5）如果（4）的条件不成立，就再往下做判断：如果旧的根节点的左子节点的值大于 “父节点” 的值并且 “父节点” 的右子节点为空，那么就将旧的根节点的左子节点设置为 “父节点” 的右子节点，实现2棵二叉树的组合，这时候 “父节点” 就真的是 旧的根节点的左子节点的父节点，那么就不用走（6-7）的步骤。

（6）如果（5）的条件不成立，就又往下做判断：如果 “父节点” 的左子节点不为空，“父节点” 就指向 “父节点” 的左子节点，那么旧的 “父节点” 的左子节点就成为了新的 “父节点”，就不用往下走（7）的步骤，而后间接又回到步骤（3）去。

（7）如果（6）的条件不成立，就又再往下做判断：“父节点” 的右子节点不为空，“父节点” 就指向 “父节点” 的右子节点，那么旧的 “父节点” 的右子节点就成为了新的 “父节点”，而后间接又回到步骤（3）去。

在删除根节点的状况中，根节点没有子节点而进行删除根节点、根节点只有左子树而进行删除根节点和根节点只有右子树而进行删除根节点这3个比拟好了解，而根节点左右子树都有而进行删除根节点可能没那么好了解，所以咱们举个例子，咱们先画一张图，图1所示：

图片

咱们要删除图1的根节点，那么就会变成2个二叉树，如图2所示：

图片

首先依照下面所说的规定，左子树的根节点4要比右子树的根节点11小，所以说2个二叉树组合成一棵二叉树时，右子树的根节点11会成新的二叉树的最终根节点，4节点将会成为节点11、10、13、12 中的一个子节点，因为11节点的左右节点不为空，所以节点4不能做为节点11的子节点，所以先递归往11节点的左子节点10看看，发现10节点左子节点为空且10大于4，所以4节点就成为10节点的左子节点，4节点设置成为10节点的左子节点后，就不会再递归往11节点的右子节点判断了，图2中组合成新的二叉树如图3所示：

图片

中序遍历进去的后果为：1 2 3 4 5 6 7 8 10 11 12 13 ，前面我会用代码测试一把给各位看看。

1、2 非叶子节点（该节点含有子节点但该节点又不是根节点）的删除

因为咱们的二叉树是单向的，所以咱们是判断以后结点的子结点是否须要删除结点，而不能去判断以后这个结点是不是须要删除结点，所以以后结点的子结点才是配角。

留神：咱们这里所说的删除非叶子节点是删除以后节点的子节点

删除以后节点的子节点（非叶子节点）就会存在以下几种状况，咱们将以下几种状况列出来并进行思路剖析；

1）删除以后节点的左子节点且以后节点的左子节点只有左子节点。

（1）获取以后节点的左子节点的左子节点并用一个长期变量保留它。

（2）用以后节点的左子节点指向这个长期变量，这样就实现了删除原先以后节点的左子节点。

2）删除以后节点的左子节点且以后节点的左子节点只有右子节点

（1）获取以后节点的左子节点的右子节点并用一个长期变量（咱们叫它child吧）保留它。

（2）将以后节点的左子节点置空，假如以后节点是 child 的 “父节点”。

（3）如果 child 的值小于等于 “父节点” 的值并且 “父节点” 的左子节点为空，那么就将 child 设置为 “父节点” 的左子节点，实现2棵二叉树的组合，这时候 “父节点” 就真的是 child 的父节点，那么就不用走（4-6）的步骤。

（4）如果（3）的条件不成立，就再往下做判断：如果 child 的值大于 “父节点” 的值并且 “父节点” 的右子节点为空，那么就将 child 设置为 “父节点” 的右子节点，实现2棵二叉树的组合，这时候 “父节点” 就真的是 child 的父节点，那么就不用走（5-6）的步骤。

（5）如果（4）的条件不成立，就又往下做判断：如果 “父节点” 的左子节点不为空，“父节点” 就指向 “父节点” 的左子节点，那么旧的 “父节点” 的左子节点就成为了新的 “父节点”，就不用往下走（6）的步骤，而后间接又回到步骤（3）去。

（6）如果（5）的条件不成立，就又再往下做判断：“父节点” 的右子节点不为空，“父节点” 就指向 “父节点” 的右子节点，那么旧的 “父节点” 的右子节点就成为了新的 “父节点”，而后间接又回到步骤（3）去。

就拿图1的二叉树来说，如果删除5节点，那么删除后图1的中序遍历为：1 2 3 4 6 7 8 9 10。

3）删除以后节点的左子节点且以后节点的左子节点都有左右子节点

（1）获取以后节点的左子节点的左子节点并用一个长期变量（咱们叫它 child1）保留它。

（2）获取以后节点的左子节点的右子节点并用一个长期变量（咱们叫它 child2）保留它。

（3）用以后节点的左子节点指向 child1，把 child1 假如为 “父节点”。

（4）如果 child2 的值小于等于 “父节点” 的值并且 “父节点” 的左子节点为空，那么就将 child2 设置为 “父节点” 的左子节点，实现2棵二叉树的组合，这时候 “父节点” 就真的是 child2 的父节点，那么就不用走（5-7）的步骤。

（5）如果（4）的条件不成立，就再往下做判断：如果 child2 的值大于 “父节点” 的值并且 “父节点” 的右子节点为空，那么就将 child2 设置为 “父节点” 的右子节点，实现2棵二叉树的组合，这时候 “父节点” 就真的是 child2 的父节点，那么就不用走（6-7）的步骤。

（6）如果（5）的条件不成立，就又往下做判断：如果 “父节点” 的左子节点不为空，“父节点” 就指向 “父节点” 的左子节点，那么旧的 “父节点” 的左子节点就成为了新的 “父节点”，就不用往下走（7）的步骤，而后间接又回到步骤（3）去。

（7）如果（6）的条件不成立，就又再往下做判断：“父节点” 的右子节点不为空，“父节点” 就指向 “父节点” 的右子节点，那么旧的 “父节点” 的右子节点就成为了新的 “父节点”，而后间接又回到步骤（3）去。

就拿图1来举个例子吧，咱们要删除4节点，因为4节点的左子节点2比4节点的右子节点7小，所以根节点的左子节点就变成了7节点，而后2节点就以7节点为 “父节点”，发现7节点的左右子节点不为空，而后先递归7节点的左子节点5，把5节点当做是新的 “父节点”，发现5节点的左子节点为空且2节点的值（序号为2嘛）比5节点的值（序号为5嘛）小，所以5节点的左子节点就是2节点，删除图1中的4节点后，图1中的二叉树变成如下图4所示：

图片

图4中二叉树中序遍历的后果为：1 2 3 5 6 7 8 9 10 11 12 13。

4）删除以后节点的右子节点且以后节点的右子节点只有右子节点。

（1）获取以后节点的右子节点的右子节点并用一个长期变量保留它。

（2）用以后节点的右子节点指向这个长期变量，这样就实现了删除原先以后节点的右子节点。

5）删除以后节点的右子节点且以后节点的右子节点只有左子节点。

（1）获取以后节点的右子节点的左子节点并用一个长期变量（咱们叫它child）保留它。

（2）将以后节点的右子节点置空，假如以后节点是 child 的 “父节点”。

（3）如果 child 的值小于等于 “父节点” 的值并且 “父节点” 的左子节点为空，那么就将 child 设置为 “父节点” 的左子节点，实现2棵二叉树的组合，这时候 “父节点” 就真的是 child 的父节点，那么就不用走（4-6）的步骤。

（4）如果（3）的条件不成立，就再往下做判断：如果 child 的值大于 “父节点” 的值并且 “父节点” 的右子节点为空，那么就将 child 设置为 “父节点” 的右子节点，实现2棵二叉树的组合，这时候 “父节点” 就真的是 child 的父节点，那么就不用走（5-6）的步骤。

（5）如果（4）的条件不成立，就又往下做判断：如果 “父节点” 的左子节点不为空，“父节点” 就指向 “父节点” 的左子节点，那么旧的 “父节点” 的左子节点就成为了新的 “父节点”，就不用往下走（6）的步骤，而后间接又回到步骤（3）去。

（6）如果（5）的条件不成立，就又再往下做判断：“父节点” 的右子节点不为空，“父节点” 就指向 “父节点” 的右子节点，那么旧的 “父节点” 的右子节点就成为了新的 “父节点”，而后间接又回到步骤（3）去。

6）删除以后节点的右子节点且以后节点的右子节点都有左右子节点

（1）获取以后节点的右子节点的左子节点并用一个长期变量（咱们叫它 child1）保留它。

（2）获取以后节点的右子节点的右子节点并用一个长期变量（咱们叫它 child2）保留它。

（3）用以后节点的右子节点指向 child1，把 child1 假如为 “父节点”。

（4）如果 child2 的值小于等于 “父节点” 的值并且 “父节点” 的左子节点为空，那么就将 child2 设置为 “父节点” 的左子节点，实现2棵二叉树的组合，这时候 “父节点” 就真的是 child2 的父节点，那么就不用走（5-7）的步骤。

（5）如果（4）的条件不成立，就再往下做判断：如果 child2 的值大于 “父节点” 的值并且 “父节点” 的右子节点为空，那么就将 child2 设置为 “父节点” 的右子节点，实现2棵二叉树的组合，这时候 “父节点” 就真的是 child2 的父节点，那么就不用走（6-7）的步骤。

（6）如果（5）的条件不成立，就又往下做判断：如果 “父节点” 的左子节点不为空，“父节点” 就指向 “父节点” 的左子节点，那么旧的 “父节点” 的左子节点就成为了新的 “父节点”，就不用往下走（7）的步骤，而后间接又回到步骤（3）去。

（7）如果（6）的条件不成立，就又再往下做判断：“父节点” 的右子节点不为空，“父节点” 就指向 “父节点” 的右子节点，那么旧的 “父节点” 的右子节点就成为了新的 “父节点”，而后间接又回到步骤（3）去。

1、3 叶子节点的删除

这里删除叶子节点时，也是不能间接把以后节点当作叶子节点，应该把以后节点的左子节点或者以后节点的右子节点当做叶子节点，删除步骤如下：

（1）如果以后结点的左子结点不为空，并且左子结点就是要删除结点，就将 this.left=nul 并且就返回(完结递归删除)。

（2）如果以后结点的右子结点不为空，并且右子结点就是要删除结点，就将 this.right=null; 并且就返回(完结递归删除)。

（3）如果第（1）和第（2）步没有删除结点,那么咱们就须要向左子树进行递归删除。

（4）如果第（3）步也没有删除结点，则该当向右子树进行递归册除。

好，说了那么多，咱们写一下代码测试一把；

（1）节点类 Node ：

public class Node {
private int no;
private Node left;
private Node right;

public Node(int no) {

super();this.no = no;

}

public int getNo() {

return no;

}

public Node getLeft() {

return left;

}

public void setLeft(Node left) {

this.left = left;

}

public Node getRight() {

return right;

}

public void setRight(Node right) {

this.right = right;

}

@Override
public String toString() {

return "Node [no=" + no + "]";

}

}

（2）主程序类 Test ：

public class Test {
private Node root;

public static void main(String[] args) {

}

// 二叉树的中序遍历
private void infixOrder() {

if (root == null) {  System.out.println("这是一棵空的二叉树，无奈进行中序遍历");} else {  infixOrder(root);}

}

// 中序遍历
private void infixOrder(Node node) {

if (node.getLeft() != null) {  infixOrder(node.getLeft());}System.out.println(node);if (node.getRight() != null) {  infixOrder(node.getRight());}

}

private void deleteNode(int no) {

if (root == null) {  System.out.println("这是一棵空二叉树，无奈删除节点");  return;}if (!deleteRoot(no)) {  boolean isSuccess = deleteNode(root, no);  if (isSuccess) {    System.out.println("删除" + no + "节点胜利");  } else {    System.out.println("没有该" + no + "节点，删除失败");  }} else {  System.out.println("删除根节点胜利");}

}

private boolean deleteRoot(int no) {

// 要删除的节点是根节点if (root.getNo() == no) {  // 要删除的根节点，没有左子树和右子树  if (root.getLeft() == null && root.getRight() == null) {    root = null;    // 要删除的根节点，都有左右子树  } else if (root.getLeft() != null && root.getRight() != null) {    Node left = root.getLeft();    root = root.getRight();// 实现删除原来的 root    combinationBinaryTreeTry(root, left);    // 要删除的根节点，只有左子树  } else if (root.getLeft() != null) {    root = root.getLeft();    // 要删除的根节点，只有右子树  } else {    root = root.getRight();  }  return true;}return false;

}

/**

  • 该办法是组合一棵新的二叉树
  • @param parent
  • 父节点
  • @param left
  • 作为 parent 的子节点或者作为 parent的子节点的子节点，以此类推...
    */

private void combinationBinaryTreeTry(Node parent, Node left) {

// 如果parent的左子节点为空，那么left的no 肯定小于等于 parent的noif (parent.getLeft() == null) {  parent.setLeft(left);  // 如果这个条件满足，证实parent的左子节点不为空，那么left的no 肯定小于等于 parent的no  // 所以left不能作为parent右子节点} else if (parent.getRight() == null) {  combinationBinaryTree(parent.getLeft(), left);  // parent的左右子节点不为空} else {  combinationBinaryTree(parent.getLeft(), left);}

}

/**

  • @param parent 将要作为父节点
  • @param child 将要作为子节点
  • @param return true 则阐明组合一棵二叉树胜利
    */

private boolean combinationBinaryTree(Node parent, Node child) {

int childNo = child.getNo();int parentNo = parent.getNo();// 如果 “将要作为父节点” 的序号大于等于 “将要作为子节点”的序号// 并且 “将要作为父节点” 的左子节点是空的if (childNo <= parentNo && parent.getLeft() == null) {  parent.setLeft(child);  return true;  // 如果 “将要作为父节点” 的序号小于于 “将要作为子节点”的序号  // 并且 “将要作为父节点” 的右子节点是空的} else if (childNo > parentNo && parent.getRight() == null) {  parent.setRight(child);  return true;} boolean result = false;if (parent.getLeft() != null) {  // 递归调用 combinationBinaryTree 办法，有可能要将child挂载在parent的左子节点  //如果曾经挂载胜利，就不用在遍历 右子节点了，也就是不去执行正文1的代码了  result = combinationBinaryTree(parent.getLeft(), child);  if (result) {    return true;  }} //1、if (parent.getRight() != null) {  // 递归调用 combinationBinaryTree 办法，有可能要将child挂载在parent的右子节点  result = combinationBinaryTree(parent.getRight(), child);}return result;

}

/**

  • @param node 二叉树中的以后节点
  • @param no 要删除的节点的序号
  • @return 返回 true 示意删除胜利
    */

private boolean deleteNode(Node node, int no) {

// 如果删除的是以后节点的左子节点（非叶子节点来的），以后节点的左子节点又有左右子节点if (node.getLeft() != null && node.getLeft().getNo() == no    && node.getLeft().getLeft() != null    && node.getLeft().getRight() != null) {  Node parent = node.getLeft().getRight();  Node child = node.getLeft().getLeft();  node.setLeft(parent);//重置以后节点的左子节点  combinationBinaryTree(parent, child);  return true;  // 如果删除的是以后节点的左子节点（非叶子节点来的），以后节点的左子节点只有左子节点} else if (node.getLeft() != null && node.getLeft().getNo() == no    && node.getLeft().getLeft() != null    && node.getLeft().getRight() == null) {  Node child = node.getLeft().getLeft();  node.setLeft(null);  combinationBinaryTree(node, child);  return true;  // 如果删除的是以后节点的左子节点（非叶子节点来的），以后节点的左子节点只有右子节点} else if (node.getLeft() != null && node.getLeft().getNo() == no    && node.getLeft().getLeft() == null    && node.getLeft().getRight() != null) {  Node child = node.getLeft().getRight();  node.setLeft(null);//重置以后节点的左子节点  combinationBinaryTree(node, child);  return true;  // 如果删除的是以后节点的右子节点（非叶子节点来的），以后节点的右子节点又有左右子节点} else if (node.getRight() != null && node.getRight().getNo() == no    && node.getRight().getLeft() != null    && node.getRight().getRight() != null) {  Node parent = node.getRight().getRight();  Node child = node.getRight().getLeft();  node.setRight(parent);//重置以后节点的右子节点  combinationBinaryTree(parent, child);  return true;  // 如果删除的是以后节点的右子节点（非叶子节点来的），以后节点的右子节点只有左子节点} else if (node.getRight() != null && node.getRight().getNo() == no    && node.getRight().getLeft() != null    && node.getRight().getRight() == null) {  Node child = node.getRight().getLeft();  node.setRight(null);//重置以后节点的右子节点  combinationBinaryTree(node, child);  return true;  // 如果删除的是以后节点的右子节点（非叶子节点来的），以后节点的右子节点只有右子节点} else if (node.getRight() != null && node.getRight().getNo() == no    && node.getRight().getLeft() == null    && node.getRight().getRight() != null) {  Node right = node.getRight().getRight();  node.setRight(right);  return true;  // 删除的是以后节点的左子节点（叶子节点来的）} else if (node.getLeft() != null && node.getLeft().getNo() == no) {  node.setLeft(null);  return true;  // 删除的是以后节点的右子节点（叶子节点来的）} else if (node.getRight() != null && node.getRight().getNo() == no) {  node.setRight(null);  return true;}boolean deleteResult = false;//向左子节点递归if (node.getLeft() != null) {  deleteResult = deleteNode(node.getLeft(), no);  if (deleteResult) {    return true;  }}//向右子节点递归if (node.getRight() != null) {  deleteResult = deleteNode(node.getRight(), no);}return deleteResult;

}

// 创立一棵二叉树
private void createBinaryTree() {

Node[] nodes = new Node[13];for (int i = 0; i < nodes.length; i++) {  nodes[i] = new Node(i + 1);}root = nodes[8];// 根节点的序号为9root.setLeft(nodes[3]);// 设置根节点的左子节点（序号为4）root.setRight(nodes[10]);// 设置根节点的右子节点（序号为11）nodes[10].setLeft(nodes[9]);// 设置11节点的左子节点（序号为10）nodes[10].setRight(nodes[12]);// 设置11节点的右子节点（序号为13）nodes[12].setLeft(nodes[11]);// 设置13节点的左子节点（序号为12）nodes[3].setLeft(nodes[1]);// 设置4节点的左子节点（序号为2）nodes[1].setLeft(nodes[0]);// 设置2节点的左子节点（序号为1）nodes[1].setRight(nodes[2]);// 设置2节点的右子节点（序号为3）nodes[3].setRight(nodes[6]);// 设置4节点的右子节点（序号为7）nodes[6].setLeft(nodes[4]);// 设置7节点的左子节点（序号为5）nodes[6].setRight(nodes[7]);// 设置7节点的右子节点（序号为8）nodes[4].setRight(nodes[5]);// 设置5节点的右子节点（序号为6）

}
}

好了，咱们就拿图1的二叉树测试一把；

（1）删除根节点（根节点左右子树都有而进行删除根节点的思路），程序入口调用如下所示：

public static void main(String[] args) {

Test test = new Test();// 创立图1中的二叉树test.createBinaryTree();test.deleteNode(9);// 中序遍历test.infixOrder();

}

日志打印如下所示：

图片

（2） 删除非叶子节点（删除以后节点的左子节点且以后节点的左子节点只有右子节点），删除5节点，程序入口调用如下所示：

public static void main(String[] args) {

Test test = new Test();// 创立图1中的二叉树test.createBinaryTree();test.deleteNode(5);// 中序遍历test.infixOrder();

}

日志打印如下所示：

图片

（3） 删除非叶子节点（删除以后节点的右子节点且以后节点的右子节点只有左子节点），删除13节点，程序入口调用如下所示：

public static void main(String[] args) {

Test test = new Test();// 创立图1中的二叉树test.createBinaryTree();test.deleteNode(13);// 中序遍历test.infixOrder();

}

日志打印如下所示：

图片

（4）删除非叶子节点（删除以后节点的左子节点且以后节点的左子节点都有左右子节点），删除13节点，程序入口调用如下所示：

public static void main(String[] args) {

Test test = new Test();// 创立图1中的二叉树test.createBinaryTree();test.deleteNode(4);// 中序遍历test.infixOrder();

}

日志打印如下所示：

图片

（5）删除非叶子节点（删除以后节点的右子节点且以后节点的右子节点都有左右子节点），删除11节点，程序入口调用如下所示：

public static void main(String[] args) {

Test test = new Test();// 创立图1中的二叉树test.createBinaryTree();test.deleteNode(11);// 中序遍历test.infixOrder();

}

日志打印如下所示：

图片

（6）删除叶子节点（以后节点的左子节点），删除12节点（以后节点是11），程序入口调用如下所示：

public static void main(String[] args) {

Test test = new Test();// 创立图1中的二叉树test.createBinaryTree();test.deleteNode(12);// 中序遍历test.infixOrder();

}

日志打印如下所示：

图片

（7）删除叶子节点（以后节点的右子节点），删除6节点（以后节点是5），程序入口调用如下所示：

public static void main(String[] args) {

Test test = new Test();// 创立图1中的二叉树test.createBinaryTree();test.deleteNode(6);// 中序遍历test.infixOrder();

}

日志打印如下所示：

图片