树结构入门教程-二叉树的查找操作

作者: 会上树的程序猿 | 来源:发表于2020-02-29 17:00 被阅读0次

树结构入门教程-二叉树的查找操作
数据结构与算法之美笔记——二叉查找树
二叉树堆 2019-04-17
二叉查找树的搜索、插入、删除、遍历等操作
树结构入门教程-二叉树遍历操作
数据结构 - 树 - 红黑树
树结构入门教程-二叉树的删除操作
18: 二叉树的镜像
MIT算法导论十平衡搜索树一
7天练|Day5：二叉树和堆

在上节我们对二叉树基本的操作有了一定的认识,熟悉了二叉树的三种遍历方式分别是:前序遍历和中序遍历以及后序遍历操作,这节的操作我们还会基于上节的基础上来完成的,首先来看下我们的基本需求:

需求:

我们利用二叉树的三种遍历方式来实现指定节点的查找如: heroNode=5的节点

看完了需求我们来分析下,首先来看我们的图:

图.png

首先我们需要新增节点5同时将它设置为节点3的左子节点,我们分别来看下这三种的遍历查找的思路分析:

前序遍历查找思路分析:

1.首先判断当前节点的编号(no)跟我们要查找的是否是同一个,如果是直接返回即可.
2.如果不相等,我们需要判断当前节点的左子节点是否为null,不为null则递归前序遍历去找,如果找到了就返回即可
3.如果在左子节点中没有找到,我们需要首先判断右子节点是否为null,如果不为null则递归前序遍历去找,如果找到了就返回即可

我们看完了前序遍历查找的思路分析,我们接着通过代码来实现,首先来看HeroNode的代码实现:

//节点查找方法
//前序遍历查找

/**
 *
 * @param no 要查找节点的编号
 * @return
 */
public HeroNode queryPreOrder(int no){
    //1.首先和root节点记性比较
    if (this.no == no){ //表示已经找到了
        return this;
    }
    //2.没有找打,先判断左子节点是否为null,如果不为null,则我们递归前序找
    HeroNode heroResult = null;
    if (this.left !=null){
         heroResult = this.left.queryPreOrder(no);
        if (heroResult !=null){
            return heroResult;
        }
    }
    //如果左子节点没有找到,我们继续找
    //判断右子节点是否为null,如果不为null,则我们递归前序找
    if (this.right !=null){
        heroResult = this.right.queryPreOrder(no);
    }
    return heroResult;
}

上述代码就是HeroNode的前序遍历查找的具体代码实现过程,接着我们来看二叉树中是如何来调这个前序遍历的代码的,具体代码如下:

   //前序遍历查找
public HeroNode queryPreOrder(int no){
    if (root !=null){
        return root.queryPreOrder(no);
    }else {
        return null;
    }
}

接着我们来看测试代码,首先我们需要创建节点5,具体代码如下:

 public static void main(String[] args) {
      //测试
    BinaryTree binaryTree = new BinaryTree();
    //节点的创建
    HeroNode root = new HeroNode(1, "宋江");
    HeroNode node2 = new HeroNode(2, "吴用");
    HeroNode node3 = new HeroNode(3, "卢俊义");
    HeroNode node4 = new HeroNode(4, "林冲");
    HeroNode node5 = new HeroNode(5,"关胜");
    //设置二叉树跟节点
    binaryTree.setRoot(root);
    //手动创建二叉树
    root.setLeft(node2);
    root.setRight(node3);
    node3.setRight(node4);
    //将node5设置为节点3的左子节点
    node3.setLeft(node5);

上述是节点5的创建和将它设置为节点3的左子节点,接着我们来看具体的测试代码:

   System.out.println("前序遍历查找测试:");
    HeroNode heroNode = binaryTree.queryPreOrder(5);
    if (heroNode !=null){
        System.out.printf("找到了,信息为 no=%d name= %s\t\n",heroNode.getNo(),heroNode.getName());
    }else {
        System.out.printf("没有找到,信息为 no=%d的英雄",5);
    }

来看测试结果如下图所示:

前序遍历查找测试代码.png

上图结果所示我们找到了,接着我们来看中序遍历查找的过程

中序遍历查找的思路分析

1.首先需要我们判断当前节点的左子节点是否为null,不为null则递归中序遍历去找,如果找到了就返回即可
2.如果左子节点没有找到,则跟当前节点的编号(no)跟我们要查找的是否是同一个,如果是直接返回即可,没有的话继续找.
3.我们需要首先判断右子节点是否为null,如果不为null则递归中序遍历去找,如果找到了就返回即可

接着我们通过代码来实现该过程,首先来看HeroNode的代码实现:

 //中序遍历查找
public HeroNode queryMidOrder(int no){
    //定义一个临时存储的变量
    HeroNode heroResult = null;
    //先判断左子节点是否为null,如果不为null我们递归中序遍历
    if (this.left !=null){
        heroResult = this.left.queryMidOrder(no);
        if (heroResult !=null){ //表示已经找到
            return heroResult;
        }
    }
    //2.跟当前节点(root节点)进行比较,如果是直接返回
    if (this.no == no){
        return this;
    }
    //3.右边节点找,先判断右子节点是否为null,如果不为null我们递归中序遍历
    if (this.right !=null){
        heroResult = this.right.queryMidOrder(no);
    }
    return heroResult;
}

上述代码就是HeroNode的前序遍历查找的具体代码实现过程,接着我们来看二叉树中是如何来调这个前序遍历的代码的,具体代码如下:

//中序遍历
public HeroNode queryMidOrder(int no){
    if (root !=null){
        return root.queryMidOrder(no);
    }else {
     return null;
    }
}

接着我们来看测试代码,具体代码如下:

System.out.println("中遍历查找测试:");
    HeroNode heroNode = binaryTree.queryMidOrder(5);
    if (heroNode !=null){
        System.out.printf("找到了,信息为 no=%d name= %s\t\n",heroNode.getNo(),heroNode.getName());
    }else {
        System.out.printf("没有找到,信息为 no=%d的英雄",5);
    }

测试结果如下图所示:

中序遍历测试结果图.png

上述就是中序查找的过程,我们最后来看后序遍历查找的具体过程

后序遍历查找的思路分析:

1.首先需要我们判断当前节点的左子节点是否为null,不为null则递归后序遍历去找,如果找到了就返回即可
2.我们需要首先判断右子节点是否为null,如果不为null则递归后序遍历去找,如果找到了就返回即可
3.如果右子节点没有找到,则跟当前节点的编号(no)跟我们要查找的是否是同一个,如果是直接返回即可,没有的话返回null即可.

接着我们通过代码来实现该过程,首先来看HeroNode的代码实现:

 //后序遍历查找
public HeroNode queryPostOrder(int no){
    //定义一个临时存储的变量
    HeroNode heroResult = null;
    //先判断左子节点是否为null,如果不为null我们递归后序遍历查找
    if (this.left !=null){
        heroResult = this.left.queryPostOrder(no);
        if (heroResult !=null){
            return heroResult;
        }
    }
    //2.右边节点找,先判断右子节点是否为null,如果不为null我们递归后序遍历查找
    if (this.right !=null){
        heroResult = this.right.queryPostOrder(no);
        if (heroResult !=null){
            return heroResult;
        }else {
            return null;
        }
    }
    //跟当前节点(root节点)进行比较,如果是直接返回
    if (this.no == no){
        return this;
    }
    //都没找到返回null
    return null;
}

上述代码就是HeroNode的前序遍历查找的具体代码实现过程,接着我们来看二叉树中是如何来调这个前序遍历的代码的,具体代码如下:

 //后序遍历
public HeroNode queryPostOrder(int no){
    if (root !=null){
        return root.queryPostOrder(no);
    }else {
        return null;
    }
}

接着我们来看测试代码,具体代码如下:

 System.out.println("后序遍历查找测试:");
    HeroNode heroNode = binaryTree.queryPostOrder(5);
    if (heroNode !=null){
        System.out.printf("找到了,信息为 no=%d name= %s\t\n",heroNode.getNo(),heroNode.getName());
    }else {
        System.out.printf("没有找到,信息为 no=%d的英雄",5);
    }