二叉搜索树的节点删除算法

删除节点是二叉搜索树操作中最复杂的，但对有些应用又非常重要，有必要好好研究一下。

 

一个取巧的办法：在树节点中加入一个boolean字段，比如isDeleted。需要删除一个节点时就把这个字段置为true，其他操作比如find()在查找之前先判断这个节点是否已经标记为删除了，这样删除的节点将不会改变树的结构，当然这样做还会继续保留这种已经删除的节点。对某些应用场景，这种做法是有优势的，比如已经离职的员工档案要保留在员工记录中。

 

下面来实现这个删除节点的算法。首先列出树节点的数据结构：

 

/**
 * @author Sun Kui
 */
public class Node {
    // node key
    public int iData;
    // node value
    public double dData;
    public Node leftChild;
    public Node rightChild;

    public Node() {
        this(0, 0.0);
    }

    public Node(int id, double dd) {
        this.iData = id;
        this.dData = dd;
    }

    public void displayNode() {
        System.out.print('{');
        System.out.print(iData);
        System.out.print(", ");
        System.out.print(dData);
        System.out.print("} ");
    }
    
    @Override
    public String toString() {
        return iData + "=>" + dData;
    }
}

 

 

 

删除节点首先从查找要删除的节点入手：

 

        Node cur = root, parent = root;
        boolean isLeftChild = true;

        while (cur.iData != key) {
            parent = cur;
            if (key < cur.iData) {
                isLeftChild = true;
                cur = cur.leftChild;
            } else {
                isLeftChild = false;
                cur = cur.rightChild;
            }

            // no node to delete
            if (cur == null) {
                return false;
            }
        }

 

 

 

找到节点后，有三中可能的情况需要考虑：

    1.该节点是叶子节点

    2.该节点有一个子节点

    3.该节点有两个子节点

 

情况1：

要删除叶子节点，只需要改变该节点的父节点对应子字段的值，代码如下：

 

       if (cur.leftChild == null && cur.rightChild == null) {
            if (cur == root) {
                // remove root node
                root = null;
            } else if (isLeftChild) {
                cur.leftChild = null;
            } else {
                cur.rightChild = null;
            }
        }

 

 

情况2：

要删除的节点有一个子节点（左子节点或者右子节点），要从二叉搜索树中”剪断“这个节点，并把它的子节点连接到它的父节点上，这个过程要求改变父节点的适当引用，指向要删除的子节点。一共有4种情况：要删除的子节点可能有左子节点或者右子节点，并且每种情况中的要删除节点也可能是自己父节点的左子节点或者右子节点。另外还有一种特殊情况：被删除的节点可能是根节点，它没有父节点，只是被合适的子树代替。代码如下：

 

       else if (cur.leftChild == null) {
            // left child node is null
            if (cur == root) {
                root = cur.rightChild;
            } else if (isLeftChild) {
                parent.leftChild = cur.rightChild;
            } else {
                parent.rightChild = cur.rightChild;
            }
        } else if (cur.rightChild == null) {
            // right child node is null
            if (cur == root) {
                root = cur.leftChild;
            } else if (isLeftChild) {
                parent.leftChild = cur.leftChild;
            } else {
                parent.rightChild = cur.leftChild;
            }
        }

 

 

情况3：

要删除有两个子节点的节点，要用其中序后继节点来代替该节点。找后继节点的算法如下：首先找到初始节点的右子节点，它的关键字值一定比初始节点大。然后转到初始节点的右子节点的左子节点（如果有的话），然后继续到该左子节点的左子节点，顺着左子节点的路径一直向下找。这个路径的最后一个左子节点就是初始节点的后继。代码如下：

 

/**
     * Returns node with next highest value after node to delete goes to right
     * child, then right child's left descendants
     * 
     * This method assume that the node to delete has right child, for it's has
     * been checked in previous in delete() method.
     * 
     * @param node
     *            to delete
     */
    private Node getSuccessor(Node delNode) {
        Node successorParent = delNode;
        Node successor = delNode;
        // go to right child of node to delete
        Node current = delNode.rightChild;

        // loop until no more left children
        while (current != null) {
            successorParent = successor;
            successor = current;
            // go to left child
            current = current.leftChild;
        }

        // if successor is not right child, make connections,prepared for deletion
        if (successor != delNode.rightChild) {
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delNode.rightChild;
        }

        return successor;
    }

 

找到后继节点以后，后继节点可能与要删除的节点有两种位置关系：后继节点可能是要删除节点的右子节点，也可能是其左子孙节点。如果是右子节点情况就简单了一些，只需要把以后继节点为根的子数移到要删除节点的位置。否则要进行更复杂的操作，情形3的完整代码如下：

 

    else {
            // two children, so replace with in-order successor
            // get successor
            Node successor = getSuccessor(cur);

            // connect parent of current to successor instead
            if (cur == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.leftChild = successor;
            } else {
                parent.rightChild = successor;
            }
            // connect successor to current's left child
            successor.leftChild = cur.leftChild;
        }
        return true;

 

请注意，getSuccessor()的代码中，已经完整了删除的部分操作。

 

最后贴出二叉搜索树删除节点算法的完整代码：

 

public boolean delete(int key) {
        Node cur = root, parent = root;
        boolean isLeftChild = true;

        while (cur.iData != key) {
            parent = cur;
            if (key < cur.iData) {
                isLeftChild = true;
                cur = cur.leftChild;
            } else {
                isLeftChild = false;
                cur = cur.rightChild;
            }

            // no node to delete
            if (cur == null) {
                return false;
            }
        }

        if (cur.leftChild == null && cur.rightChild == null) {
            if (cur == root) {
                // remove root node
                root = null;
            } else if (isLeftChild) {
                cur.leftChild = null;
            } else {
                cur.rightChild = null;
            }
        } else if (cur.leftChild == null) {
            // left child node is null
            if (cur == root) {
                root = cur.rightChild;
            } else if (isLeftChild) {
                parent.leftChild = cur.rightChild;
            } else {
                parent.rightChild = cur.rightChild;
            }
        } else if (cur.rightChild == null) {
            // right child node is null
            if (cur == root) {
                root = cur.leftChild;
            } else if (isLeftChild) {
                parent.leftChild = cur.leftChild;
            } else {
                parent.rightChild = cur.leftChild;
            }
        } else {
            // two children, so replace with in-order successor
            // get successor
            Node successor = getSuccessor(cur);

            // connect parent of current to successor instead
            if (cur == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.leftChild = successor;
            } else {
                parent.rightChild = successor;
            }
            // connect successor to current's left child
            successor.leftChild = cur.leftChild;
        }
        return true;
    }

 

测试代码如下：

import java.util.Random;

/**
 * @author Sun Kui
 */
public class Main {
    public static void main(String... args) {
        BinarySearchTree theTree = new BinarySearchTree();
        if (args.length < 1) {
            System.out.println("Usage: java Main number");
            return;
        }

        int count = Integer.parseInt(args[0]);
        Random rand = new Random();
        for (int i = 0; i < count; i++) {
            theTree.insert(rand.nextInt(count * count), rand.nextDouble() + 1);
        }
        
        theTree.insert(35, 1.8);

        Node found = theTree.find(35);
        System.out.println(found);
        theTree.inOrder(theTree.getRootNode());
    }
}

 

 end.