MENU

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

November 25, 2018 • Read: 487 • 算法

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

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

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

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

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

  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;
}
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment