查找二叉排序树中小于key的数的个数 用c+
时间: 2024-10-21 10:11:58 浏览: 0
查找二叉排序树(Binary Search Tree, BST)中小于给定键值(key)的节点数量,通常需要遍历树来进行计数。以下是一个简单的C++函数实现,用于计算小于`key`的节点数:
```cpp
#include <iostream>
// 定义二叉搜索树结点结构体
struct Node {
int data;
Node* left;
Node* right;
};
// 创建新节点
Node* createNode(int value) {
Node* newNode = new Node();
if (!newNode) return nullptr; // 如果分配内存失败,返回nullptr
newNode->data = value;
newNode->left = newNode->right = nullptr;
return newNode;
}
// 插入操作保持BST特性
Node* insert(Node* root, int key) {
if (root == nullptr) return createNode(key); // 空树直接插入
if (key < root->data)
root->left = insert(root->left, key);
else if (key > root->data)
root->right = insert(root->right, key);
return root;
}
// 计算小于key的节点数
int countNodesLessThan(Node* root, int key) {
if (root == nullptr) return 0; // 如果根为空,说明树也为空,返回0
if (root->data < key) return 1 + countNodesLessThan(root->right, key); // 左子树递归,加上当前节点
else return countNodesLessThan(root->left, key); // 否则继续左子树
}
// 示例用法
int main() {
Node* root = nullptr;
root = insert(root, 50); // 插入一些数据构建BST
// ... (后续可以继续插入数据)
int targetKey = 45; // 搜索小于这个key的数量
int result = countNodesLessThan(root, targetKey);
std::cout << "Number of nodes less than " << targetKey << ": " << result << std::endl;
return 0;
}
```
阅读全文