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

    public void delete(int key){
        if(root==null) return;
        Node currentNode=root;
        Node parentNode=root;

        //定位到要删除的key 的父节点,以及当前元素
        while(currentNode!=null&&currentNode.key!=key){
            parentNode=currentNode;
            if(currentNode.key>key){
                currentNode=currentNode.left;
            }else{
                currentNode=currentNode.right;
            }

        }

        System.out.println("要删除的是："+currentNode.key);
        System.out.println("父亲是："+parentNode.key);
//       要替换删除元素的node
        Node exNode=min(currentNode.right);
        System.out.println("与其替换的是："+exNode.key);
        //找到其右节点中最小节点用以替换要删除的节点
        if(parentNode.key>key){
            parentNode.left=exNode;

        }else{
            parentNode.right=exNode;
        }
        deleteMin(currentNode.right); //删除原引用
        if(exNode!=null){
            //将新节点中的左右子节点更新为要删除元素的左右节点
            if(currentNode.left!=null&&exNode.key!=currentNode.left.key) //防止当子节点就是替代节点的时候引起死循环
            exNode.left=currentNode.left; 
            if(currentNode.right!=null&&exNode.key!=currentNode.right.key)
            exNode.right=currentNode.right;
        }
        currentNode.left=null;
        currentNode.right=null;


    }

中序遍历，其他遍历也差不多，不多讲

 public void inOrder(Node rootNode) { //中序遍历
                 if (rootNode != null) {
                     inOrder(rootNode.left);
                      System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value);
                     inOrder(rootNode.right);
                  }
              }

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