树结构

image.png

code

BinarySortTreeNode

package com.pl.arithmetic.binarySortTree;

import com.pl.arithmetic.dto.HeroNode;

/**
 * <p>
 *
 * @Description: TODO
 * </p>
 * @ClassName BinarySortTreeNode
 * @Author pl
 * @Date 2020/10/13
 * @Version V1.0.0
 */
public class BinarySortTreeNode {
    private int value;
    private String name;
    BinarySortTreeNode leftNode;
    BinarySortTreeNode rightNode;

    public BinarySortTreeNode(int value, String name) {
        this.value = value;
        this.name = name;
    }


    public BinarySortTreeNode(int value) {
        this.value = value;
    }

    /**
     *前序排序
     * 
     * @param 
     * @return void
     * @exception 
     * @author silenter
     * @date 2020/10/13 7:04
    */
    public void preOrder(){
        System.out.println(this.value);
        if (this.leftNode!=null){
            this.leftNode.preOrder();
        }
        if (this.rightNode!=null){
            this.rightNode.preOrder();
        }
    }

    /**
     *中序排序
     * 
     * @param 
     * @return void
     * @exception 
     * @author silenter
     * @date 2020/10/13 7:04
    */
    public void infixOrder(){
        if (this.leftNode!=null){
            this.leftNode.infixOrder();
        }
        System.out.println(this.value);
        if (this.rightNode!=null){
            this.rightNode.infixOrder();
        }
    }

    /**
     *后续排序
     *
     * @param
     * @return void
     * @exception
     * @author silenter
     * @date 2020/10/13 7:05
    */
    public void postOrder(){
        if (this.leftNode!=null){
            this.leftNode.postOrder();
        }
        if (this.rightNode!=null){
            this.rightNode.postOrder();
        }
        System.out.println(this.value);
    }


    /**
     *前需查找
     *
     * @param no
     * @return com.pl.arithmetic.binarySortTree.BinarySortTreeNode
     * @exception
     * @author silenter
     * @date 2020/10/20 7:31
    */
    public BinarySortTreeNode preOrderSearch(int no) {
        System.out.println("进入遍历");
        BinarySortTreeNode binarySortTreeNode = null;
        if (no == this.value){
            return this;
        }
        if (this.leftNode!=null){
            binarySortTreeNode = this.leftNode.preOrderSearch(no);
        }
        if (binarySortTreeNode == null && this.rightNode!=null){
            binarySortTreeNode = this.rightNode.preOrderSearch(no);
        }
        return binarySortTreeNode;
    }

    /**
     *中序查找
     *
     * @param no
     * @return com.pl.arithmetic.dto.HeroNode
     * @exception
     * @author silenter
     * @date 2020/10/20 7:44
    */
    public BinarySortTreeNode infixOrderSearch(int no) {
        BinarySortTreeNode binarySortTreeNode = null;
        if (this.leftNode!=null){
            binarySortTreeNode = this.leftNode.infixOrderSearch(no);
        }
        if (binarySortTreeNode != null)
            return binarySortTreeNode;
        //注意放在当前节点上，真正比较查找比较，是在拿当前节点比较，比较了几次也就是查找了几次。
        System.out.println("进入遍历");
        if (this.value == no)
            return this;
        if (this.rightNode!=null)
            binarySortTreeNode = this.rightNode.infixOrderSearch(no);
        return binarySortTreeNode;
    }

    /**
     * 后续查找
     *
     * @param no
     * @return com.pl.arithmetic.binarySortTree.BinarySortTreeNode
     * @exception
     * @author silenter
     * @date 2020/10/20 7:50
    */
    public BinarySortTreeNode postOrderSearch(int no) {

        BinarySortTreeNode binarySortTreeNode = null;
        if (this.leftNode!=null){
            binarySortTreeNode = this.leftNode.infixOrderSearch(no);
        }
        if (binarySortTreeNode != null)
            return binarySortTreeNode;
        if (this.rightNode!=null)
            binarySortTreeNode = this.rightNode.infixOrderSearch(no);
        if (binarySortTreeNode != null)
            return binarySortTreeNode;
        System.out.println("进入遍历");
        if (this.value == no)
            return this;
        return binarySortTreeNode;
    }


    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public BinarySortTreeNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(BinarySortTreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public BinarySortTreeNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(BinarySortTreeNode rightNode) {
        this.rightNode = rightNode;
    }

    public String getName() {
        return name;
    }

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

BinarySortTree

package com.pl.arithmetic.binarySortTree;

/**
 * <p>
 *
 * @Description: TODO
 * </p>
 * @ClassName BinarySortTree
 * @Author pl
 * @Date 2020/10/13
 * @Version V1.0.0
 */
public class BinarySortTree {
    private BinarySortTreeNode root;


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

    public void preOrder(){
        if(verifyRootNode()){
            this.root.preOrder();
        }
    }

    public void infixOrder(){
        if(verifyRootNode()){
            this.root.preOrder();
        }
    }

    public void postOrder(){
        if(verifyRootNode()){
            this.root.preOrder();
        }
    }

    public BinarySortTreeNode preOrderSearch(int no) {
        return root.preOrderSearch(no);
    }

    public BinarySortTreeNode infixOrderSearch(int no) {
        return root.infixOrderSearch(no);
    }

    public BinarySortTreeNode postOrderSearch(int no) {
        return root.postOrderSearch(no);
    }


    public boolean verifyRootNode(){
        if (this.root!=null){
            return true;
        }
        System.out.println("root为空");
        return false;
    }
}

TestDemo

package com.pl.arithmetic.binarySortTree;

import com.pl.arithmetic.dto.HeroNode;

/**
 * <p>
 *
 * @Description: TODO
 * </p>
 * @ClassName TestDemo
 * @Author pl
 * @Date 2020/10/20
 * @Version V1.0.0
 */
public class TestDemo {
    public static void main(String[] args) {
        BinarySortTreeNode root = new BinarySortTreeNode(1, "tom");
        BinarySortTreeNode node2 = new BinarySortTreeNode(2, "jack");
        BinarySortTreeNode node3 = new BinarySortTreeNode(3, "smith");
        BinarySortTreeNode node4 = new BinarySortTreeNode(4, "mary");
        BinarySortTreeNode node5 = new BinarySortTreeNode(5, "king");

        //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeftNode(node2);
        root.setRightNode(node3);
        node3.setRightNode(node4);
        node3.setLeftNode(node5);

        BinarySortTree binarySortTree = new BinarySortTree();
        binarySortTree.setRoot(root);

        //4次
        BinarySortTreeNode binarySortTreeNode = binarySortTree.preOrderSearch(5);
        System.out.println("中序查找！！！！！！！！！！！");
        //3
        BinarySortTreeNode binarySortTreeNode2 = binarySortTree.infixOrderSearch(5);
        System.out.println("后序查找！！！！！！！！！！");
        //2
        BinarySortTreeNode binarySortTreeNode3 = binarySortTree.postOrderSearch(5);


    }
}

image.png

notice

真正比较寻找的是这个代码块

 if (no == this.value){
            return this;
        }

当前节点上，真正比较查找比较，是在拿当前节点比较，比较了几次也就是查找了几次。