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

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

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

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

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

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

false

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

首先看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;
}