关于java:Java版二叉树的删除

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）的步骤。

就拿图 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 的“父节点”。

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

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

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

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

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 的 no
if (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];// 根节点的序号为 9
root.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();

}

日志打印如下所示：

图片