首先,我们知道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.
假设一棵树中的键是唯一的,并且我们知道所有键的值。
我的想法
我有一个天真的解决方案,即为每个可能的键调用搜索算法,并计算该函数返回 true 的次数。
但是我想减少调用函数的次数,同时也想提高时间复杂度。我的直觉告诉我,递归 可能很有用,但我不确定。
我认为对于每个节点,我们需要有关其父(或祖先)的信息,因此我考虑过如下定义二叉树数据结构
struct node {
int key;
struct node* left;
struct node* right;
struct node* parent; // Adding a 'parent' pointer may be useful....
};
我真的想不出一种有效的方法来判断一个节点是否可搜索,我也想不出一个方法来找出可搜索节点的数量。因此,我来到这里寻求帮助。提示比完整的解决方案更好。
这是我第一次在 Stack Overflow 上提问。如果您认为这篇文章需要改进,请随时发表评论。感谢阅读。
最佳答案
要计算可以找到的键,您应该遍历树并跟踪从根部获取的路径所暗示的范围(低,高)。因此,当您从具有键 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;
}
关于algorithm - 使用 BST 搜索算法查找一般二叉树中可以搜索的节点数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/67109470/