二分搜索树之查找(Search)-包含(Contain)

一. 查找(Search)

1. 逻辑

前面我们了解了对节点的插入，其实在二分搜索树中对相应节点的查找的过程中也有同样的逻辑

下面我们来看看具体的查找(Search):

我们在树中查找键值为42的节点

1. 将42和41比较，42 > 41,根据二分搜索树的定义可知，我们应该继续往41节点的右孩子查找：
2. 
3. 此时再将42和58比较，42 < 58,继续向58节点的左孩子节点查找
4. 
5. 42 < 50,继续向50节点的左孩子查找，此时50节点的左孩子就为42，所以我们就找到了节点42，并返回对应的value值
6. 

如果我们要查找的节点不存在，则返回空或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);
}