使用二叉搜索树搜索算法可以在一般二叉树中找到的节点数量

Question

首先，我们知道二叉搜索树的搜索算法如下：

// 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);

}

这种搜索算法通常应用于二叉搜索树，但是对于一般的二叉树，这种算法可能会给我们带来错误的结果。

下面的问题让我困扰了很长时间。

给定一棵一般的二叉树，使用上述BST搜索算法可以找到其中多少个节点？

以下面的二叉树为例。可搜索的节点已用颜色标出，因此答案为3。

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

我的想法

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

然而，我想减少调用函数的次数，并改进时间复杂度。我的直觉告诉我，递归可能很有用，但我不确定。

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

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

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

这是我第一次在Stack Overflow上提问。如果您认为这篇文章需要改进，请随时留下评论。谢谢阅读。

- rogeryen

---

你提到的彩色树和“可搜索”节点的例子，从一般算法上看，对我来说是完全无法理解的。为什么只有蓝色节点可以被搜索？而且，将BST搜索算法应用于一般（我想是未排序的）二叉树会得出任何答案，因为您正在尝试错误的算法或数据结构，无论您认为哪个错了。 - Vroomfondel

我假设一切都是关于使用BST属性找到节点的第一个根节点。 - nice_dev

Answer 1

要计算可以找到的键的数量，您应该遍历树并跟踪由从根节点开始的路径所暗示的范围（low，high）。因此，当您从具有键值5的节点向左移动时，您应该考虑您不能再找到任何比5更大（或相等，因为该值已经计算过）的值。如果该节点的左子节点具有键值2，并且您向右走，则知道您不能再找到任何小于2的值。因此，此时您的窗口已缩小为（2、5）。如果该窗口变为空，则在该方向的树中深入挖掘没有意义。

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

#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;
}

- trincot

Answer 2

以下属性对于解决这个问题非常重要。

任何符合BST属性的二叉树节点都可以使用BST搜索算法进行搜索。

考虑你分享的例子。

.

现在，假设

1. 如果您正在搜索1 => 那么它将在第一次命中时成功。 (Count =1)

2. 对于2，它将在1的右子树中搜索。在6处，没有找到左子树，因此未找到。

3. 对于6，在1的右子树中搜索。找到匹配！ (Count =2)

4. 同样地，对于7，在1的右子树中搜索，然后在6的搜索之后进行搜索。找到匹配！ (Count =3)

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

另一个有趣的模式是，每当节点遵循BST节点属性时，计数器都会递增。

其中一个重要的属性是：

• 根节点的值大于所有根节点的左侧值，并小于所有根节点的右侧值。

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

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

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

- Phenomenal One

---

你需要让这更加清晰明了，因为它现在不太有意义。 - Abhinav Mathur

这不会起作用。要考虑2是否是一个有效的BST节点。即使是有效节点，它也不会被检测到。 - Abhinav Mathur

你能提供一个例子吗？2在右边还是左边？如果是右边，那它就在6的左边。 - Phenomenal One

我在谈论所给图片中的树。 - Abhinav Mathur