二叉搜索树移除方法

Question

我正在制作一个按字符串键排序的二叉搜索树。每个节点由一个与一个键相关联的无序信息链表组成。这棵树是按字母顺序排列的。

我已经完成了大部分的程序，但有麻烦的删除方法。

谢谢你。

//My attempt:
//Removes node with corresponding k
public void remove(String k) {
    rootNode = remove(rootNode, k);
}

//Recursive method:
private KeyNode remove(KeyNode x, String k) {
    if (x == null) {
        return x;
    }
    //int comparison with compareTo
    //if less than 0, left node = remove(left node, k)
    //if greater than 0, right node = remove(right node, k)
    //if left node and right node are both null, return null
    //if left node is null, return left node
    //if right node is null, return right node
    //return
}

Answer 1

你可以做这样的事

public rootNode remove (String k, rootNode n) {
    if (n == null)
        return null;

    if (k.compareTo(n.key)<0)
        remove (k, n.leftChild);
    else if (k.compareTo(n.key)>0)
        remove (k, n.rightChild);
    else {
        if (n.leftChild != null && n.rightChild != null)    {
            /* n has two children, find max from left then 
             * switch it with n and remove n */

        }
        else if(n.leftChild != null) {
            /* n has a left child only then left child replaces n 
             * and n is deleted */


        }
        else if(n.rightChild != null) {
            /* n has a right child only then right child replaces n
             * and n is deleted*/

        }
        else {
            n = null;
        }
    }

}