使用 BST 搜索算法查找一般二叉树中可以搜索的节点数

Question

首先，我们知道BST的搜索算法是这样的：

// Function to check if given key exists in given BST.
bool search (node* root, int key) 
{
    if (root == NULL)
        return false;

    if (root->key == key)
        return true;

    if (root->key > key)
        return search(root->left, key);

    else
        return search(root->right, key);

}

这种搜索算法通常应用在二叉搜索树中。但是，当涉及到一般的二叉树时，这样的算法可能会给出错误的结果。

下面这个问题困了我好久

Given a general binary tree, count how many nodes in it can be found using the BST searching algorithm above.

以下面的二叉树为例。彩色节点是可搜索的，所以答案是 3.

假设一棵树中的键是唯一的，并且我们知道所有键的值。

我的想法

我有一个天真的解决方案，就是为每个可能的键调用搜索算法，并计算函数 returns 为真的次数。

但是我想减少调用函数的次数，同时也想提高时间复杂度。我的直觉告诉我递归可能有用，但我不确定。

我认为对于每个节点，我们需要有关其父（或祖先）的信息，因此我考虑过如下定义二叉树数据结构

struct node {
    int key;
    struct node* left;
    struct node* right;
    struct node* parent;        // Adding a 'parent' pointer may be useful....
};

我真的想不出一种有效的方法来判断一个节点是否可搜索，我也想不出一个方法来找出可搜索节点的数量。因此，我来到这里寻求帮助。提示比完整的解决方案更好。

这是我第一次在 Stack Overflow 上提问。如果您认为此 post 需要改进，请随时发表评论。感谢阅读。

Answer 1

下面的属性对解决这道题很重要

Any binary tree node which respects the BST properties will always be searchable using BST Search Algorithm.

考虑您分享的示例。

.

现在，假设

如果你搜索的是1 => 那么会导致第一次命中成功。（计数 =1）
对于2，它会在1的右子树中查找。在6时，没有找到左子树，因此没有找到。
对于 6，在 1 的右子树中搜索。找到匹配项！（计数 =2）
与7类似，在1的右子树中搜索，然后在6中搜索。找到匹配项！（计数 =3）

现在，当在列表中搜索从 0 到 max(nodes) 的所有数字时，计数器会递增。

另一个有趣的模式，您可以看到，只要节点跟随 BST 节点属性.

，计数器就会递增

其中一个重要的属性是：

根节点的值大于所有根的左值且小于所有根的右值。

例如，考虑节点 7：它位于 6 的右侧和 1 的右侧。因此是一个有效节点。

考虑到这一点，问题可以分解为一棵树中有效 BST 节点的数量。

解决这个问题非常简单。您尝试使用 Tree 从上到下遍历并检查它是否按递增顺序排列。如果不是，则无需检查其子项。如果是，则将计数器加 1 并检查其子项。

Answer 2

要计算可以找到的键，您应该遍历树并跟踪从根部开始的路径所隐含的范围（低，高）。因此，当您从具有键 5 的节点向左移动时，您应该考虑再也找不到任何大于大于 5（或等于，因为该值已经计算在内）的值为了）。如果该节点的左子节点有键 2，而你向右转，那么你就知道你找不到任何比 2 less 的值了。所以你的 window在那一刻缩小到 (2, 5)。如果那个 window 变成空的，那么在树的那个方向深入挖掘就没有意义了。

这是一种您可以使用递归轻松应用的算法。这是一些代码：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct node {
    int key;
    struct node* left;
    struct node* right;
} Node;

Node *create_node(int key, Node *left, Node *right) {
    Node * node = malloc(sizeof(struct node));
    node->key = key;
    node->left = left;
    node->right = right;
    return node;
}

int count_bst_nodes_recur(Node *node, int low, int high) {
    return node == NULL || node->key <= low || node->key >= high ? 0
         : 1 + count_bst_nodes_recur(node->left, low, node->key)
             + count_bst_nodes_recur(node->right, node->key, high);
}

int count_bst_nodes(Node *node) {
    return count_bst_nodes_recur(node, -INT_MAX, INT_MAX);
}

int main(void) {
    // Create example tree given in the question:
    Node *tree = create_node(1,
        create_node(2,
            create_node(4, NULL, NULL),
            create_node(5, NULL, NULL)
        ),
        create_node(6,
            NULL,
            create_node(7, NULL, NULL)
        )
    );

    printf("Number of searchable keys: %d\n", count_bst_nodes(tree)); // -> 3
    return 0;
}

使用 BST 搜索算法查找一般二叉树中可以搜索的节点数

Find the number of nodes in a general binary tree that can be searched using BST searching algorithm

algorithm

search

tree

binary-tree

binary-search-tree