二分搜索树的层序遍历

 二分搜索树的层序遍历,即逐层进行遍历,即将每层的节点存在队列当中,然后进行出队(输出节点)和入队(存入下一层的节点)的操作,以此达到遍历的目的

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author BestQiang
 */
public class BST2<E extends Comparable> {
    // 树的节点类
    class Node {
        E e;
        Node left;
        Node right;
        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
        }
    }

    // 声明树的根节点
    private Node root;
    //声明树的大小
    private int size;

    public BST2() {
        this.root = null;
        this.size = 0;
    }

    // 获取二分搜索树的大小
    public int getSize() {
        return size;
    }

    // 判断二分搜索树是否为空树
    public boolean isEmpty() {
        return size == 0;
    }

    // 为二分搜索树添加不重复的元素
    public void add(E e) {
        root = add(root, e);
    }

    private Node add(Node node, E e) {
        if(node == null) {
            return new Node(e);
        }
        if(e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else {
            node.right = add(node.right, e);
        }
        return node;
    }

    // 二分搜索树的层序遍历
    public void levleOrder() {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()) {
            Node cur = q.remove();
            System.out.println(cur.e);
            if(cur.left != null) {
                q.add(cur.left);
            }
            if(cur.right != null) {
                q.add(cur.right);
            }
        }
    }

    public static void main(String[] args) {
        BST2<Integer> bst = new BST2<>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for(int num: nums)
            bst.add(num);

        /////////////////
        //      5      //
        //    /   \    //
        //   3    6    //
        //  / \    \   //
        // 2  4     8  //
        /////////////////
        bst.levleOrder();
        System.out.println();
    }

}

输出结果:

5
3
6
2
4
8