Board logo

标题: 二叉查找树实现原理分析(7) [打印本页]

作者: look_w    时间: 2019-1-11 18:31     标题: 二叉查找树实现原理分析(7)

ceiling的实现
ceiling()则与floor()相反,它做的是向下取整,即找到大于等于key的最小结点。但是两者的实现思路是一致的,只要将上面的左变为右,小于变为大于就行了:
/**
* Returns the smallest key in the symbol table greater than or equal to {@code key}.
*
* @param  key the key
* @return the smallest key in the symbol table greater than or equal to {@code key}
* @throws NoSuchElementException if there is no such key
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public Key ceiling(Key key) {
    if(key == null) {
        throw new IllegalArgumentException("argument to ceiling() is null");
    }
    if(isEmpty()) {
        throw new NoSuchElementException("called ceiling() with empty symbol table");
    }
    Node x = ceiling(root, key);
    if(x == null) {
        return null;
    } else {
        return x.key;
    }
}
private Node ceiling(Node x, Key key) {
    if(x == null) {
        return null;
    } else {
        int cmp = key.compareTo(x.key);
        if(cmp == 0) {
            return x;
        } else if(cmp < 0) {
            Node t = ceiling(x.left, key);
            if (t != null) {
                return t;
            } else {
                return x;
            }
        } else {
            return ceiling(x.right, key);
        }
    }
}





欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) Powered by Discuz! 7.0.0