二分搜索树系列之「查找(Search)-包含(Contain)」

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

一. 查找(Search)

1. 逻辑

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

  1. 将42和41比较,42 > 41,根据二分搜索树的定义可知,我们应该继续往41节点的右孩子查找:
    二分搜索树系列之【查找(Search)-包含(Contain)】

  2. 此时再将42和58比较,42 < 58,继续向58节点的左孩子节点查找
    二分搜索树系列之【查找(Search)-包含(Contain)】

  3. 42 < 50,继续向50节点的左孩子查找,此时50节点的左孩子就为42,所以我们就找到了节点42,并返回对应的value值
    二分搜索树系列之【查找(Search)-包含(Contain)】

如果我们要查找的节点不存在,则返回空或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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!