二叉排序树 删除 二叉搜索树非递归实现(2)

返回该节点最小节点，就是一直遍历往左遍历直到找到其左子节点为空那么当前节点就是最小的。二叉排序树 删除

    public Node min(Node node){ //返回node下最小节点
        //当前节点为空直接返回，不为空找到其左子节点为空为止
        Node currentNode=node;
        if(currentNode==null)
            return null;
        while(currentNode.left!=null){
            currentNode=currentNode.left;
        }
        return currentNode;

    }

删除元素操作在二叉树的操作中应该是比较复杂的。首先来看下比较简单的删除最大最小值得方法。

以删除最小值为例，我们首先找到最小值，及最左边左子树为空的节点，然后返回其右子树作为新的左子树。

public void deleteMin(Node node){ //删除该节点下的最小节点
        Node currentNode=node;
        Node parentNode=node;
        if(currentNode==null)
            return;
        //先定位到key，不用已经写好的find方法而自己写是因为find方法是从根开始的，有些地方的用到这个函数不用从根开始
        //一直往左深入，直到它的左子节点为null，然后将其右子节点替换掉该节点（如无右节点即为null）。
        while(currentNode.left!=null){

            parentNode=currentNode;
            currentNode=currentNode.left;
        }
        parentNode.left=currentNode.right; 
        currentNode.right=null;

    }

    public void deleteMax(Node node){
        //做法与min相似
        Node currentNode=node;
        Node parentNode=node;
        if(currentNode==null)
            return;

        while(currentNode.right!=null){
            parentNode=currentNode;
            currentNode=currentNode.right;
        }
        parentNode.right=currentNode.left; 
    currentNode.left=null;

    }

删除的一般情况，上述删除最大和最小只是两个特殊情况，有了上面做铺垫下面的就好理解点，首先我们需要找到待删除节点的左子树上的最大值节点，或者右子树上的最小值节点（T.Hibbard提出的一种解决方法），然后将该节点的参数值与待删除的节点参数值进行交换，最后删除该节点，这样需要删除的参数就从该二叉树中删除了。需要注意的是删除后的一些引用该置为null的一定要置为null好让其被回收。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-68005-2.html