极简数据结构 - 二叉树

二叉搜索树(只包含插入、深度遍历、广度遍历)

public class Tree {

    private Node root;

    public static class Node{

        private Integer value;
        private Node left;
        private Node right;

        public Node(Integer value) {
            this.value = value;
        }
    }

    public void add(Integer e){
        if(root == null){
            root = new Node(e);
        } else {
            recursionAdd(root, e);
        }
    }

    public void recursionAdd(Node node, Integer key){
        if(key > node.value){
            if(node.right == null){
                node.right = new Node(key);
            }else{
                recursionAdd(node.right, key);
            }
        } else {
            if(node.left == null){
                node.left = new Node(key);
            } else {
                recursionAdd(node.left, key);
            }
        }
    }

    /**
     * 深度优先遍历
     */
    public void deepOutPut(){
        recursionScan(root);
    }
    
    public void recursionScan(Node node){
        if(node == null){
            return;
        }
        recursionScan(node.left);
        // 中序遍历
        System.out.println(node.value);
        recursionScan(node.right);
    }

    /**
     * 广度优先遍历
     */
    public void breadthOutPut(){
        BlockingQueue<Node> blockingQueue = new LinkedBlockingQueue();
        blockingQueue.add(root);
        while (!blockingQueue.isEmpty()){
            Node poll = blockingQueue.poll();
            if(poll != null){
                System.out.println(poll.value);
                if(poll.left != null){
                    blockingQueue.add(poll.left);
                }

                if(poll.right != null){
                    blockingQueue.add(poll.right);
                }
            }
        }
    }

    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.add(2);
        tree.add(1);
        tree.add(3);
        tree.add(-5);
        tree.add(3);
        tree.add(3);
        tree.add(0);
        System.out.println("<=======深度优先遍历=======>");
        tree.deepOutPut();
        System.out.println("<=======广度优先遍历=======>");
        tree.breadthOutPut();
    }
}