判断搜索二叉树、完全二叉树

如何判断一棵树是搜索二叉树

搜索二叉树的定义是：二叉树中任一结点的右结点都比自己大，左节点都比自己小

判断方式很简单：二叉树中序遍历，判断遍历的结点值是否是升序即可

如何判断一棵树是完全二叉树

分两种情况来判断是否是完全二叉树：

1. 对于某一个结点，有右结点没有左结点，直接返回false
2. 对于一个结点，如果有左结点，没有右结点，或者左右结点都没有，那么之后遍历的结点必须都是叶子结点

举个例子，对于任意给定的二叉树（例如下图所示），按层遍历，依次判断上面的情况

首先看0号结点，有左也有右；遍历到1号结点，有左也有右；遍历到2号结点，有左也有右；遍历到3号结点，有左也有右；遍历到4号结点，满足上面第二种情况了，所以开启一个阶段，这个阶段导致后面所有遍历到的结点，必须是叶子结点；5是叶子结点，6是叶子节点，7,8,9都是叶子结点，此时遍历完了，没有任何错误，返回true

还是上图，如果将9改为4的右结点，当遍历到4的时候，因为违反了第一条规则，所以直接返回false了

public static boolean isCBT(Node head) {
    if(head == null)
        return true;
    Queue<Node> q = new LinkedList<Node>();
    boolean leaf = flase;
    Node l = null;
    Node r = null;
    q.offer(head);
    while(!q.isEmpty()) {
        head = q.poll();
        l = head.left;
        r = head.right;
        if((leaf && (l != null || r != null)) || (l == null && r != null))
            return false;
        if(l != null)
            q.offer(l);
        if(r != null);
            q.offer(r);
        else // l != null && r == null
            leaf = true;
    }
    return true;
}