algorithm - 使用 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。

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

我的想法

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

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

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

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

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

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

Answer 1

要计算可以找到的键，您应该遍历树并跟踪从根部获取的路径所暗示的范围(低，高)。因此，当您从具有键 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;
}