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

一. 查找(Search)

1. 逻辑

前面我们了解了对节点的插入，其实在二分搜索树中对相应节点的查找的过程中也有同样的逻辑
下面我们来看看具体的查找(Search):
我们在树中查找键值为42的节点

1. 将42和41比较，42 > 41,根据二分搜索树的定义可知，我们应该继续往41节点的右孩子查找：
   

2. 此时再将42和58比较，42 < 58,继续向58节点的左孩子节点查找
   

3. 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 协议》，转载必须注明作者和本文链接