博客

思路分析

前序查找：

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

这里我子介绍前序查找的思路，中序和后序查找的思路和前序查找的思路差不多

代码

/**
 * 模拟结点
 */
public class Node {
    private int id;
    private String name;
    /*左节点*/
    private Node left;
    /*右节点*/
    private Node right;
	/*分别用来计算前中后序查找进行了多少次*/
    public static int preCount = 0;
    public static int midCount = 0;
    public static int postCount = 0;

    /*构造方法*/
    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    /**
     * 根据ID前序查找
     * @param id ID
     * @return 如果找到就返回Node 没有找到就返回null
     */
    public Node preQuery(int id){
        preCount++;
        /*比较当前结点是不是要查找的结点*/
        if (this.id == id) {
            return this;
        }
        Node resNode = null;
        if (this.left != null) {
            /*如果左子结点*不为空,就递归前序查找左子树*/
            resNode = this.left.preQuery(id);
        }
        if (resNode != null) {
            /*在左子树中找到目标结点*/
            return resNode;
        }
        if (this.right != null) {
            /*如果右子结点*不为空,就递归前序查找右子树*/
            resNode = this.right.preQuery(id);
        }
        return resNode;
    }

    /**
     * 根据ID中序查找
     * @param id ID
     * @return 如果找到就返回Node 没有找到就返回null
     */
    public Node midQuery(int id){
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.midQuery(id);
        }
        if (resNode != null) {
            /*在左子树中找到目标结点*/
            return resNode;
        }
        /*比较当前结点是不是要查找的结点*/
        midCount++;
        if (this.id == id) {
            return this;
        }
        if (this.right != null) {
            resNode = this.right.midQuery(id);
        }
        return resNode;
    }

    /**
     * 根据ID后序查找
     * @param id ID
     * @return 如果找到就返回Node 没有找到就返回null
     */
    public Node postQuery(int id){
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.postQuery(id);
        }
        if (resNode != null) {
            /*在左子树中找到目标结点*/
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.postQuery(id);
        }
        if (resNode != null) {
            /*在右子树中找到目标结点*/
            return resNode;
        }
        postCount++;
        if (this.id == id) {
            return this;
        }
        return resNode;
    }
    
	setter and getter 方法
	
    @Override
    public String toString() {
        return "[" + "id=" + id + ", name=" + name  + ']';
    }
}

/**
 * 模拟二叉树
 */
public class BinaryTree {

    /*根结点*/
    private Node root;

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

    /*前序查找*/
    public Node preSearch(int id){
        if (this.root != null) {
            return this.root.preQuery(id);
        }else {
            return null;
        }
    }

    /*中序查找*/
    public Node midSearch(int id){
        if (this.root != null) {
            return this.root.midQuery(id);
        }else {
            return null;
        }
    }

    /*后序查找*/
    public Node postSearch(int id){
        if (this.root != null) {
            return this.root.postQuery(id);
        }else {
            return null;
        }
    }
}

/**
 * 测试类
 */
public class BinaryTreeTest {
    public static void main(String[] args) {
        /*手动创建结点*/
        Node node1 = new Node(1,"张三");
        Node node2 = new Node(2,"李四");
        Node node3 = new Node(3,"王五");
        Node node4 = new Node(4,"赵六");
        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);

        /*创建二叉树*/
        BinaryTree tree = new BinaryTree();
        tree.setRoot(node1);

        System.out.print("前序查找：");
        Node resNode1 = tree.preSearch(1);
        System.out.print(resNode1==null ? "未找到目标" : resNode1);
        System.out.println(" 前序查找一种查找了"+Node.preCount+"次");//1

        System.out.print("中序查找：");
        Node resNode2 = tree.midSearch(1);
        System.out.print(resNode2==null ? "未找到目标" : resNode2);
        System.out.println(" 中序查找一种查找了"+Node.midCount+"次");//2

        System.out.print("后序查找：");
        Node resNode3 = tree.postSearch(1);
        System.out.print(resNode3==null ? "未找到目标" : resNode3);
        System.out.println(" 后序查找一种查找了"+Node.postCount+"次");//4
    }
}

运行结果

前序查找：[id=1, name=张三] 前序查找一种查找了1次
中序查找：[id=1, name=张三] 中序查找一种查找了2次
后序查找：[id=1, name=张三] 后序查找一种查找了4次

Process finished with exit code 0