2023年6月22日发(作者：)

⼆叉树算法删除代码实现此代码仅供参考，如有疑问欢迎评论：⼆叉树的删除操作⽐较复杂，主要分三种情况：1、删除没有⼦节点的节点，2、删除只有⼀个节点的节点（其中有分为两种情况），3、删除有两个节点的节点。在讲解之前我先把查找的代码附上，以为删除过程需要⽤到这段⼉查找的代码： public TreeNode search( int key) { TreeNode pNode = root ; while (pNode != null ) { if (key == pNode. key ) { return pNode; } else if (key > pNode. key ) { pNode = pNode. rchild ; } else if (key < pNode. key ) { pNode = pNode. lchild ; } } return null ; // 如果没有搜索到结果那么就只能返回空值了 }⾸先看第⼀种情况：（删除没有⼦节点的节点） 删除没有⼦节点的节点只需要将被删除节点的⽗节点指向空即可 if (pNode. lchild == null && pNode. rchild == null ) { if (pNode == root ) { //如果是根节点，那么就删除整棵树 root = null ; } else if (pNode == pNode. parent . lchild ){ //如果这个节点是⽗节点的左节点，则将⽗节点的左节点设为空 pNode. parent . lchild = null ; } else if (pNode == pNode. parent . rchild ) { //如果这个节点是⽗节点的右节点，则将⽗节点的右节点设为空 pNode. parent . rchild = null ; } }第⼆种情况：（删除只有⼀个⼦节点的节点） 删除有⼀个⼦节点的节点，只需要将被删除节点的⽗节点指向删除节点的⼦节点即可

//第⼆种情况： （删除有⼀个⼦节点的节点） //如果要删除的节点只有右节点 if (pNode. lchild == null && pNode. rchild != null ) { if (pNode == root ) { root = pNode. rchild ; } else if (pNode == pNode. parent . lchild ) { pNode. parent . lchild = pNode. rchild ; pNode. rchild . parent = pNode. parent ; } else if (pNode == pNode. parent . rchild ) { pNode. parent . rchild = pNode. rchild ; pNode. rchild . parent = pNode. parent ; } } //如果要删除的节点只有左节点 if (pNode. lchild != null && pNode. rchild == null ) { if (pNode == root ) { root = pNode. lchild ; } else if (pNode == pNode. parent . lchild ) { pNode. parent . lchild = pNode. lchild ; pNode. lchild . parent = pNode. parent ; } else if (pNode == pNode. parent . rchild ) { pNode. parent . rchild = pNode. lchild ; pNode. lchild . parent = pNode. parent ; } }第三种情况：（删除有两个⼦节点的节点，即左右⼦树都⾮空） 删除有两个⼦节点的节点，到底谁来替代被删除的节点的位置呢？是左节点，还是右节点，代替以后这个⼦节点的⼦节点应该怎么安排？⼀系列的问题都出来了。。。简便的⽅法就是要找⼀个节点代替这个被删除的节点，这就要从⼆叉搜索树的定义来看。因为⼆叉搜索树是有序的，我们要找的节点在这棵树上，⽽且这个节点要⽐被删除的左节点⼤，⽐右节点⼩。先看看这个已被删除节点的右节点为根的⼦树的所有节点的值都要⽐被删除节点⼤，这是⼆叉搜索树定义的，但是要在这个集合中找到最⼩的⼀个，来代替被删除的节点，那就要在这棵⼦树上⼀直往左找。这个节点⽐被删除的节点的右节点⼩，且⽐左节点⼤，那这个节点就叫做被删除节点的后继节点，⽤这个节点来代替被删除节点。

// 从⼆叉树当中删除指定的节点 public void delete( int key) throws Exception { TreeNode pNode = search(key); if (pNode == null ) { throw new Exception( "此树中不存在要删除的这个节点！" ); } delete(pNode); } //这个⽅法可以算是⼀个递归的⽅法，适⽤于 要删除的节点的两个⼦节点都⾮空， //并且要删除的这个节点的后续节点也有⼦树的情况下 private void delete(TreeNode pNode) throws Exception { // 第⼀种情况:删除没有⼦节点的节点 if (pNode. lchild == null && pNode. rchild == null ) { if (pNode == root ) { // 如果是根节点，那么就删除整棵树 root = null ; } else if (pNode == pNode. parent . lchild ) { // 如果这个节点是⽗节点的左节点，则将⽗节点的左节点设为空 pNode. parent . lchild = null ; } else if (pNode == pNode. parent . rchild ) { // 如果这个节点是⽗节点的右节点，则将⽗节点的右节点设为空 pNode. parent . rchild = null ; } } // 第⼆种情况： （删除有⼀个⼦节点的节点） // 如果要删除的节点只有右节点 if (pNode. lchild == null && pNode. rchild != null ) { if (pNode == root ) { root = pNode. rchild ; } else if (pNode == pNode. parent . lchild ) { pNode. parent . lchild = pNode. rchild ; pNode. rchild . parent = pNode. parent ; } else if (pNode == pNode. parent . rchild ) { pNode. parent . rchild = pNode. rchild ; pNode. rchild . parent = pNode. parent ; } } // 如果要删除的节点只有左节点 if (pNode. lchild != null && pNode. rchild == null ) { if (pNode == root ) { root = pNode. lchild ; } else if (pNode == pNode. parent . lchild ) { pNode. parent . lchild = pNode. lchild ; pNode. lchild . parent = pNode. parent ; } else if (pNode == pNode. parent . rchild ) { pNode. parent . rchild = pNode. lchild ; pNode. lchild . parent = pNode. parent ; } } // 如果要删除的节点有两个⼦节点，即左右⼦节点都⾮空 // ⽅法是⽤要删除的节点的后续节点代替要删除的节点，并且删除后续节点（删除后续节点的时候同样的递归操作） // 其实，这⾥要⽤到的最多也就会发⽣两次，即后续节点不会再继续递归的删除下⼀个后续节点了 // 因为，要删除的节点的后续节点肯定是 要删除的那个节点的右⼦树的最⼩关键字，⽽这个最⼩关键字肯定不会有左节点 // 所以，在删除后续节点的时候肯定不会⽤到（ 两个节点都⾮空的判断 ），如有有⼦节点，肯定就是有⼀个右节点。 if (pNode. lchild != null && pNode. rchild != null ) { // 先找出后续节点 TreeNode successorNode = successor(pNode); if (pNode == root ) { root . key = successorNode. key ; } else { pNode. key = successorNode. key ; //赋值，将后续节点的值赋给要删除的那个节点 } delete(successorNode); //递归的删除后续节点 } }附上完整的代码： import ist;

import ;

public class BinarySearchTree {

private TreeNode root = null;// 树的根节点

//⽤于保存节点的列表

private List nodeList = new ArrayList();

private class TreeNode {

private int key;// 节点关键字

private TreeNode parent;

private TreeNode lchild;

private TreeNode rchild;

public TreeNode(int key, TreeNode parent, TreeNode lchild,

TreeNode rchild) {

= key;

= parent;

= lchild;

= rchild;

}

public String toString() {

String lKey = (lchild == null) ? "" : f();

String rKey = (rchild == null) ? "" : f();

return "(" + lKey + "<-" + key + "->" + rKey + ")";

}

}

// 判断是否为空

public boolean isEmpty() {

if (root == null) {

return true;

} else {

return false;

}

}

// 如果树是空的情况下就抛出异常

public void TreeEmpty() throws Exception {

if (isEmpty()) {

throw new Exception("这棵树是空树！");

}

}

// 插⼊操作

public void insert(int key) {

TreeNode parentNode = null;

TreeNode newNode = new TreeNode(key, null, null, null);

TreeNode pNode = root;

if (root == null) {

root = newNode;

return;

}

while (pNode != null) {

parentNode = pNode;

if (key > ) {

pNode = ;

} else if (key < ) {

pNode = ;

} else { // 树中已经存在此值，⽆需再次插⼊

return;

}

}

if (key > ) {

= newNode;

= parentNode;

} else if (key < ) {

= newNode;

= parentNode;

}

}

// 搜索关键字

public TreeNode search(int key) {

TreeNode pNode = root;

while (pNode != null) {

if (key == ) {

return pNode;

} else if (key > ) {

pNode = ;

} else if (key < ) {

pNode = ;

}

}

return null;// 如果没有搜索到结果那么就只能返回空值了

}

// 获取⼆叉树的最⼩关键字节点

public TreeNode minElemNode(TreeNode node) throws Exception {

if (node == null) {

throw new Exception("此树为空树！");

}

TreeNode pNode = node;

while ( != null) {

pNode = ;

}

return pNode;

}

// 获取⼆叉树的最⼤关键字节点

public TreeNode maxElemNode(TreeNode node) throws Exception {

if (node == null) {

throw new Exception("此树为空树！");

}

TreeNode pNode = node;

while ( != null) {

pNode = ;

}

return pNode;

}

// 获取给定节点在中序遍历下的后续节点

public TreeNode successor(TreeNode node) throws Exception {

if (node == null) {

throw new Exception("此树为空树！");

}

// 分两种情况考虑，此节点是否有右⼦树

// 当这个节点有右⼦树的情况下，那么右⼦树的最⼩关键字节点就是这个节点的后续节点

if ( != null) {

return minElemNode();

}

// 当这个节点没有右⼦树的情况下,即 == null

// 如果这个节点的⽗节点的左⼦树 与 这个节点相同的话，那么就说明这个⽗节点就是后续节点了

// 难道这⾥还需要进⾏两次if语句吗？不需要了，这⾥⽤⼀个while循环就可以了

TreeNode parentNode = ;

while (parentNode != null && == node) {

node = parentNode;

parentNode = ;

} return parentNode;

}

// 获取给定节点在中序遍历下的前趋结点

public TreeNode precessor(TreeNode node) throws Exception {

// 查找前趋节点也是分两种情况考虑

// 如果这个节点存在左⼦树，那么这个左⼦树的最⼤关键字就是这个节点的前趋节点

if ( != null) {

return maxElemNode();

}

// 如果这个节点不存在左⼦树，那么这个节点的⽗节点

TreeNode parentNode = ;

while (parentNode != null && == node) {

node = parentNode;

parentNode = ;

}

return parentNode;

}

// 从⼆叉树当中删除指定的节点

public void delete(int key) throws Exception {

TreeNode pNode = search(key);

if (pNode == null) {

throw new Exception("此树中不存在要删除的这个节点！");

}

delete(pNode);

}

//这个⽅法可以算是⼀个递归的⽅法，适⽤于 要删除的节点的两个⼦节点都⾮空，

//并且要删除的这个节点的后续节点也有⼦树的情况下

private void delete(TreeNode pNode) throws Exception {

// 第⼀种情况:删除没有⼦节点的节点

if ( == null && == null) {

if (pNode == root) {// 如果是根节点，那么就删除整棵树

root = null;

} else if (pNode == ) {

// 如果这个节点是⽗节点的左节点，则将⽗节点的左节点设为空

= null;

} else if (pNode == ) {

// 如果这个节点是⽗节点的右节点，则将⽗节点的右节点设为空

= null;

}

}

// 第⼆种情况： （删除有⼀个⼦节点的节点）

// 如果要删除的节点只有右节点

if ( == null && != null) {

if (pNode == root) {

root = ;

} else if (pNode == ) {

= ;

= ;

} else if (pNode == ) {

= ;

= ;

}

}

// 如果要删除的节点只有左节点

if ( != null && == null) {

if (pNode == root) {

root = ;

} else if (pNode == ) {

= ;

= ;

} else if (pNode == ) {

= ;

= ;

}

} // 如果要删除的节点有两个⼦节点，即左右⼦节点都⾮空

// ⽅法是⽤要删除的节点的后续节点代替要删除的节点，并且删除后续节点（删除后续节点的时候同样的递归操作）

// 其实，这⾥要⽤到的最多也就会发⽣两次，即后续节点不会再继续递归的删除下⼀个后续节点了

// 因为，要删除的节点的后续节点肯定是 要删除的那个节点的右⼦树的最⼩关键字，⽽这个最⼩关键字肯定不会有左节点

// 所以，在删除后续节点的时候肯定不会⽤到（ 两个节点都⾮空的判断 ），如有有⼦节点，肯定就是有⼀个右节点。

if ( != null && != null) {

// 先找出后续节点

TreeNode successorNode = successor(pNode);

if (pNode == root) {

= ;

} else {

= ;//赋值，将后续节点的值赋给要删除的那个节点

}

delete(successorNode);//递归的删除后续节点

}

}

//中序遍历⼆叉树，并获得节点列表

public List inOrderTraverseList() {

if(nodeList != null) {

();

}

inOrderTraverse(root);

return nodeList;

}

//进⾏中序遍历

private void inOrderTraverse(TreeNode node) {

if(node != null) {

inOrderTraverse();

(node);

inOrderTraverse();

}

}

//获取⼆叉查找树中关键字的有序列表

public String toStringOfOrderList() {

StringBuilder sb = new StringBuilder("[");

for(TreeNode pNode : nodeList) {

( + " ");

}

("]");

return ng();

}

}