/** * Created by elvalad on 2014/12/5. * 按层遍历二叉查找树 */import java.util.Iterator;import java.util.LinkedList;public class PrintBST<Key extends Comparable<Key>, Value> {    private Node root;  /* 根节点 */    private int N;      /* 节点数 */    private class Node {        Key key;        /* 键 */        Value val;      /* 值 */        Node left;      /* 左子树 */        Node right;     /* 右子树 */        Node(Key key, Value val) {            this.key = key;            this.val = val;        }    }    public void put(Key key, Value val) {        root  = put(root, key, val);        N++;    }    private Node put(Node x, Key key, Value val) {        if (x == null) {            return new Node(key, val);        }        int cmp = key.compareTo(x.key);        if (cmp < 0) {            x.left = put(x.left, key, val);        } else if (cmp > 0) {            x.right = put(x.right, key, val);        } else {            x.val = val;        }        return x;    }    public int height(Node x) {        if (x == null)            return 0;        int lh = height(x.left);        int rh = height(x.right);        return (lh > rh) ? (lh + 1) : (rh + 1);    }    /* 使用队列将每个节点按一定的顺序入队出队，遍历队列中的元素即可 */    public void printBST(Node x) {        if (x == null)            return;        LinkedList<Node> lln = new LinkedList<Node>();        lln.add(x);        while (!lln.isEmpty()) {            Node first  = lln.getFirst();            System.out.println(first.key);            if (first.left != null) {                lln.add(first.left);            }            if (first.right != null) {                lln.add(first.right);            }            lln.remove();        }    }    public static void main(String[] args) {        PrintBST<String, Integer> pbst = new PrintBST<String, Integer>();        pbst.put("DDDD", 4);        pbst.put("CCC", 3);        pbst.put("A", 1);        pbst.put("BB", 2);        pbst.put("FFFFFF", 6);        pbst.put("EEEEE", 5);        pbst.printBST(pbst.root);    }}