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

二叉树的前序、中序、后序查找

查找指定节点

• 请编写前序查找，中序查找和后序查找的方法。
• 并分别使用三种查找方式，查找heroNO=5的节点
• 并分析各种查找方式，分别比较了多少次

前序查找思路

1. 先判断当前结点的no是否等于要查找的
2. 如果是相等，则返回当前结点
3. 如果不等，则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
4. 如果左递归前序查找，找到结点，则返回，否续判断，当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找.

中序查找思路

1. 判断当前结点的左子节点是否为空，如果不为空，则递归查找
2. 如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点，否则继续进行右递归的中序查找
3. 如果右递归中序查找，找到就返回，否则返回null

后序查找思路

1. 判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
2. 如果找到，就返回，如果没有找到，就判断当前结点的右子节点是否为空，如果不为空，则右递归进行后序查找，如果找到，就返回
3. 就和当前结点进行，比如，如果是则返回，否则返回null

代码实现

代码语言：javascript复制

//前序遍历查找
/**
 *
 * @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;
}

代码语言：javascript复制

//中序遍历查找
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;
}

代码语言：javascript复制

//后序遍历查找
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;
}

二叉树节点的删除

• 如果删除的节点是叶子节点，则删除该节点
• 如果删除的节点是非叶子节点，则删除该子树
• 测试，删除掉5号叶子节点和3号子树.

思路分析

考虑如果树是空树oot,如果只有一个root结点，则等价将二叉树置空

1.因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点

2.如果当前结点的左子结点不为空，并且左子结点就是要除结点，就将this.left=null;并且就返回（结束递归删除)

3.如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null:并且就返回（结束递归删除)

4.如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除

5.如果第4步也没有删除结点，则应当向右子树进行递归删除

代码实现

代码语言：javascript复制

//递归删除节点
//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);
    }
}

java 数据结构

0 人点赞