查找和插入操作的实现
查找操作
我们先来看一下如何在二叉树中根据指定的键查找到它相关联的结点。查找会有两种结果：查找成功或者不成功，我们以查找成功的情形来分析一下整个查找的过程。前面我们提到了二叉查找树的一个重要特征就是：左子树的结点都要小于根结点，右子树的结点都要大于根结点。根据这一性质，我们从根结点开始遍历二叉树，遍历的过程中会出现3种情况：
- 如果查找的键key小于根结点的key，说明我们要查找的键如果存在的话肯定在左子树，因为左子树中的结点都要小于根结点，接下来我们继续递归遍历左子树。
- 如果要查找的键key大于根结点的key，说明我们要查找的键如果存在的话肯定在右子树中，因为右子树中的结点都要大于根节点，接下来我们继续递归遍历右子树。
- 如果要查找的键key等于根结点的key，那么我们就直接返回根结点的val。
二叉树查找流程图
上面的操作我们利用递归可以非常容易的实现，代码如下：
/**
* Returns the value associated with the given key.
*
* @param key the key
* @return the value associated with the given key if the key is in the symbol table
* and null if the key is not in the symbol table
* @throws IllegalArgumentException if key is null
*/
public Value get(Key key) {
if(key == null) {
throw new IllegalArgumentException("first argument to put() is null");
} else {
return get(root, key);
}
}
private Value get(Node x, Key key) {
if(x == null) {
return null;
} else {
int cmp = key.compareTo(x.key);
if(cmp < 0) {
return get(x.left, key);
} else if(cmp > 0) {
return get(x.right, key);
} else {
return x.val;
}
}
}
|
