java数据结构和算法——二叉树的前序遍历、中序遍历和后序遍历查询指定节点

一、二叉树的前序遍历、中序遍历和后序遍历概念

• 前序遍历: 先输出父节点，再遍历左子树和右子树
• 中序遍历: 先遍历左子树， 再输出父节点，再遍历右子树
• 后序遍历: 先遍历左子树，再遍历右子树， 最后输出父节点
• 小结: 看输出父节点的顺序，就确定是前序遍历，中序遍历还是后序遍历

二、二叉树的前序遍历、中序遍历和后序遍历查询指定节点的思路图解

三、二叉树的前序遍历、中序遍历、后序遍历查询指定节点的需求

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

四、二叉树的前序遍历、中序遍历、后序遍历查询指定节点的示例代码

1、代码

package com.rf.springboot01.dataStructure.tree;

/**
 * @description: 前序遍历、中序遍历、后序遍历查询指定节点示例
 * @author: xiaozhi
 * @create: 2020-08-27 21:28
 */
public class BinaryTreeDemoTwo {
    public static void main(String[] args) {
        //创建二叉树
        BinaryTrees binaryTrees = new BinaryTrees();
        //创建需要的结点
        UserNode root = new UserNode(1,"张三");
        UserNode node2 = new UserNode(2, "李四");
        UserNode node3 = new UserNode(3, "王五");
        UserNode node4 = new UserNode(4, "小志");
        UserNode node5 = new UserNode(5, "Tom");
        //手动创建该二叉树
        binaryTrees.setRoot(root);//创建根节点
        root.setLeft(node2);//创建根节点左边子节点
        root.setRight(node3);//创建根节点右边子节点
        node3.setRight(node4);//创建根节点右边子节点的右边子节点
        node3.setLeft(node5);//创建根节点右边子节点的左边子节点

        //测试
        UserNode userNode=binaryTrees.preOrderSearch(5);
        if(userNode!=null){
            System.out.printf("前序遍历查找指定节点,找到了 no=%d name=%s 的用户",userNode.getNo(),userNode.getName());
        }else{
            System.out.printf("前序遍历查找指定节点,没有找到 no=%d 的用户",5);
        }
        System.out.println();

        UserNode userNode1=binaryTrees.infixOrderSearch(5);
        if(userNode1!=null){
            System.out.printf("中序遍历查找指定节点,找到了 no=%d name=%s 的用户",userNode1.getNo(),userNode1.getName());
        }else{
            System.out.printf("中序遍历查找指定节点,没有找到 no=%d 的用户",5);
        }
        System.out.println();

        UserNode userNode2=binaryTrees.suffixOrderSearch(5);
        if(userNode1!=null){
            System.out.printf("后序遍历查找指定节点,找到了 no=%d name=%s 的用户",userNode2.getNo(),userNode2.getName());
        }else{
            System.out.printf("后序遍历查找指定节点,没有找到 no=%d 的用户",5);
        }
        System.out.println();
    }
}

/**
 * @Description: 创建BinaryTrees 二叉树
 * @Param:
 * @Author: xz
 * @return:
 * @Date: 2020/8/27 15:03
 */
class BinaryTrees{
    private UserNode root;

    public void setRoot(UserNode root) {
        this.root = root;
    }

    //前序遍历查找指定节点
    public UserNode preOrderSearch(int no){
        if(root !=null){
            return  this.root.preOrderSearch(no);
        }else{
            return null;
        }
    }

    //中序遍历查找指定节点
    public UserNode infixOrderSearch(int no){
        if(root != null){
            return this.root.infixOrderSearch(no);
        }else {
            return null;
        }
    }

    //后序遍历查找指定节点
    public UserNode suffixOrderSearch(int no){
        if(root != null){
            return this.root.suffixOrderSearch(no);
        }else{
            return null;
        }
    }
}

/**
 * @Description: 先创建UserNode结点类
 * @Author: xz
 * @Date: 2020/8/27 14:46
 */
class UserNode{
    private int no;
    private String name;
    private UserNode left;//左节点，默认为null
    private UserNode right;//右节点，默认为null

    //构造方法
    public UserNode(int no, String name) {
        this.no = no;
        this.name = name;
    }
    //getter、setter方法
    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public UserNode getLeft() {
        return left;
    }

    public void setLeft(UserNode left) {
        this.left = left;
    }

    public UserNode getRight() {
        return right;
    }

    public void setRight(UserNode right) {
        this.right = right;
    }

    //toString方法
    @Override
    public String toString() {
        return "UserNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    /**
    * @Description:  前序遍历查找指定节点
    * @Param:  no 查找no
    * @Author: xz
    * @return: 如果找到就返回该Node ,如果没有找到返回 null
    * @Date: 2020/8/27 21:47
    */
    public UserNode preOrderSearch(int no){
        UserNode userNode =null;
        System.out.println("进入前序遍历查找指定节点");
        //判断当前节点的no是否等于需要查找的no,如果相等，则返回当前节点
        if(this.no == no){
            return this;
        }
        //如果不相等,判断当前节点的左子节点是否为空，如果不为空，则递归前序查找。
        if(this.left != null){
            userNode=this.left.preOrderSearch(no);

        }
        //如果左递归前序查找找到节点，则返回
        if(userNode !=null){
            return userNode;
        }
        // 如果左递归前序查找没有找到节点，判断当前节点的右子节点是否为空，如果不为空，则向右递归前序查找
        if(this.right != null){
            userNode=this.right.preOrderSearch(no);
        }
        return userNode;
    }

    /**
     * @Description:  中序遍历查找指定节点
     * @Param:  no 查找no
     * @Author: xz
     * @return: 如果找到就返回该Node ,如果没有找到返回 null
     * @Date: 2020/8/27 21:47
     */
    public UserNode infixOrderSearch(int no){
        UserNode userNode =null;
        //判断当前节点的左子节点是否为空，如果不为空，则递归中序查找
        if(this.left != null){
            userNode=this.left.infixOrderSearch(no);
        }
        // 如果找到，则返回
        if(userNode != null){
            return userNode;
        }
        System.out.println("进入中序遍历查找指定节点");
        //如果没有找到，就和当前节点比较，如果找到,则返回当前节点
        if(this.no == no){
            return this;
        }
        //否则继续进行右递归的中序查找，如果右递归中序查找，找到则返回，否则返回null
        if(this.right !=null){
            userNode=this.right.infixOrderSearch(no);
        }
        return userNode;
    }

    /**
     * @Description:  后序遍历查找指定节点
     * @Param:  no 查找no
     * @Author: xz
     * @return: 如果找到就返回该Node ,如果没有找到返回 null
     * @Date: 2020/8/27 21:47
     */
    public UserNode suffixOrderSearch(int no){
        UserNode userNode =null;
        //判断当前节点的左子节点是否为空，如果不为空，则递归后序查找
        if(this.left != null){
            userNode=this.left.suffixOrderSearch(no);
        }
        // 如果找到，则返回
        if(userNode != null){
            return userNode;
        }
        //如果没有找到，判断当前节点的右子节点是否为空，如果不为空,则右递归进行后续查找，
        if(this.right !=null){
            userNode=this.right.suffixOrderSearch(no);
        }
        //如果找到，则返回
        if(userNode != null){
            return userNode;
        }
        System.out.println("进入后序遍历查找指定节点");
        // 如果左子节点和右子节点都没有知道，和当前节点进行比较，如果是则返回，否则返回null
        if(this.no ==no){
            return this;
        }
        return userNode;
    }
}

2、运行main函数，输出结果如下：