二分搜索树系列之「查找(Search)-包含(Contain)」
0 / 0 / 创建于 4年前 /
iceymoss 的个人博客
二分搜索树之查找 (Search)- 包含 (Contain)#
一。查找 (Search)#
1. 逻辑#
前面我们了解了对节点的插入，其实在二分搜索树中对相应节点的查找的过程中也有同样的逻辑
下面我们来看看具体的查找 (Search):
我们在树中查找键值为 42 的节点
将 42 和 41 比较，42 > 41, 根据二分搜索树的定义可知，我们应该继续往 41 节点的右孩子查找：
此时再将 42 和 58 比较，42 < 58, 继续向 58 节点的左孩子节点查找
42 < 50, 继续向 50 节点的左孩子查找，此时 50 节点的左孩子就为 42，所以我们就找到了节点 42，并返回对应的 value 值
如果我们要查找的节点不存在，则返回空或 false
2. 代码实现 (使用递归，c++ 实现)#
在 public 中定义：
//找到key相应的节点并且返回value的地址
Node *seacher(Key key, Value value) {
return seacher(root, key, value);
}在 private 中定义：
//在二分搜索树中找到相应元素并返回该元素的地址
Value *seacher(Node *node, Key key) {
if (key == NULL)
return NULL;
//找到key 返回value的地址
if (key == node->key)
return &(node->value);
else if (key > node->key)
return seacher(node->right, key);
else return seacher(node->left, key);
}二。包含 (Contain)#
1. 逻辑#
前面我们将了” 查找”，其实” 包含” 的逻辑和” 查找” 是一样的，只是目的不同，” 查找” 的目的是找到我们需要找的节点并返回对应的地址；
*” 包含 (Contain)” 的目的是判断二分搜索树中是否存在一个节点，如果存在则返回 true，否则返回 false。*
其逻辑和操作过程和” 查找 (Search)” 一样的
2. 代码实现 (使用递归，c++ 实现)#
在 public 中定义：
//在树中寻找是否存在key
bool contain(Key key) {
return contain(root, key);
}在 private 中定义：
//在二分搜索树中查找key，存在返回trun不存在返回false
bool contain(Node *node, Key key) {
//元素不存在
if (key == NULL)
return false;
//元素存在
if (key == node->key)
return true;
else if (key > node->key)
return contain(node->right, key);
else return contain(node->left, key);
}
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号