java - 使用 T 扩展 Comparable java 检查 BT 是否为 BST

Question

检查 BT 或 BST 是否很简单，但在使用 Comparable 类时我在算法上遇到了困难。

首先，我有给定的 BT 插入方法:

public void insert(T item){
    //initialize new BT and sets left, right, parent and data to null
    BinaryTree<T> newNode = new BinaryTree<T>();
    newNode.setData(item);

    if (size==0){
        tree = newNode;
        size++;
        return;
    }

    BinaryTree<T> t = tree;
    boolean done = false;

    while (!done){
        int c = item.compareTo(t.getData());
        if (c==0){
            System.out.println("Duplicate key. Can't insert");
            return;
        }
        //need to go left
        else if (c<0){
            //place to insert found
            if (t.getLeft()==null){
                t.setLeft(newNode);
                newNode.setParent(t);
                size++;
                done = true;
            }
            else
                //otherwise go left one branch
                t = t.getLeft();
        }
        //c>0; need to go right
        else{
            //place to insert found
            if (t.getRight()==null){
                t.setRight(newNode);
                newNode.setParent(t);
                size++;
                done=true;
            }
            else
                t = t.getRight();
        }
    }
}

我将 4 2 5 1 3 插入 BT，将 1 2 3 4 插入 BT这棵树看起来像:

    4   / \  2   5 / \1   3 1  \   2    \     3      \       4

and the result still return true.

For the validation method for BST:

public static<T extends Comparable<T>> boolean isBinarySearchTree(BinaryTree<T> t){

    if(t ==null){
        return true;
    }
    if(t.getLeft()!=null && t.getLeft().getData().compareTo(t.getData())>0){
        return false;
    }
    if(t.getRight() !=null && t.getRight().getData().compareTo(t.getData())<0){
        return false;
    }
    return isBinarySearchTree(t.getLeft()) && isBinarySearchTree(t.getRight());
}

我想使用 T 扩展可比较的 <> ，并将 BinaryTree t 输入到方法中。
但是我很困惑为什么该方法仍然确定第二个 BT 也是 BST。

Answer 1

添加额外高度方法怎么样:

int height(BinaryTree bt) {
    if (bt == null) {
       return 0;
    }
    return 1 + Math.max(height(bt.getLeft()), height());
}

然后在 isBinarySearchTree 检查中添加额外的 if 语句:

if (height(t.getRight()) != height(t.getLeft())) {
    return false;
}

这会增加 O(log n) 的复杂性，因为它可能会遍历每个级别的树的高度。