Qz学算法-数据结构篇(二分查找、删除)

//前序遍历查找
/**
 *
 * @param no 查找no
 * @return 如果找到就返回该Node,如果没有找到返回null
 */
public HeroNode preOrderSearch(int no){
    //比较当前节点是不是
    if(this.no==no){
        return this;
    }
    //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
    //2.如果左递归前序查找,找到节点,则返回
    HeroNode resNode = null;
    if(this.left!=null){
        resNode = resNode.left.preOrderSearch(no);
    }
    if (resNode!=null){
        //说明左子树找到
        return resNode;
    }
    //1,左递归前序查找，找到结点，则返回，否继续判断，
    //2,当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
    if(this.right!=null){
        resNode = this.right.preOrderSearch(no);
    }
    return resNode;
}

//中序遍历查找
public HeroNode infixOrderSearch(int no){
    //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
    HeroNode resNode = null;
    if (this.left!=null){
        resNode = this.left.infixOrderSearch(no);
    }
    if (resNode!=null){
        return  resNode;
    }
    //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
    if(this.no == no){
        return this;
    }

    //否则继续进行右递归的中序查找
    if (this.right!=null){
        resNode = this.right.infixOrderSearch(no);
    }
    return resNode;
}

//后序遍历查找
public HeroNode postOrderSearch(int no){
    //判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
    HeroNode resNode = null;
    if (this.left!=null){
        resNode = this.left.postOrderSearch(no);
    }
    if (resNode!= null){
        //说明在左子树找到
        return resNode;
    }
    //如果左子树没有找到.则向右子树递归进行后序遍历查找
    if (this.right!=null){
        resNode = this.right.postOrderSearch(no);
    }
    if (resNode!=null){
        return resNode;
    }
    //如果左右子树都没有找到，就比较当前结点是不是
    if (this.no == no){
        return this;
    }
    return resNode;
}

//递归删除节点
//1.如果删除的节点是叶子节点,则删除该节点
//2.如果删除的节点是非叶子节点,则删除该子树
public void delNode(int no){
    /**
     * 1.因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点
     *
     * 2.如果当前结点的左子结点不为空，并且左子结点就是要除结点，就将this.left=null;并且就返回（结束递归删除)
     *
     * 3.如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null:并且就返回（结束递归删除)
     *
     * 4.如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
     *
     * 5.如果第4步也没有删除结点，则应当向右子树进行递归删除
     */
    //2.
    if (this.left!=null&&this.left.no == no){
        this.left = null;
        return;
    }
    //3.
    if (this.right!=null&&this.right.no==no){
        this.right=null;
        return;
    }
    //4.我们就需要向左子树进行递归删除
    if (this.left!=null){
        this.left.delNode(no);
    }
    //5.
    if (this.right!=null){
        this.right.delNode(no);
    }
}