新人求解一道数据C++结构算法题目
写一个递归函数smallcount，传入一棵二叉检索树和值K，返回值小于或等于K的结点数目。
想了半天没头绪，求算法和大神详细解释，！！！！
[解决办法]
递归。
#include <iostream>
struct tree_node
{
int elem_;
tree_node *left_;
tree_node *right_;
};
tree_node* insert(tree_node *node, int e)
{
if (!node)
{
node = new tree_node;
node->elem_ = e;
node->left_ = node->right_ = NULL;
}
else if (node->elem_ > e)
node->left_ = insert(node->left_, e);
else if (node->elem_ < e)
node->right_ = insert(node->right_, e);
return node;
}
int count_less_than_k(tree_node *root, int k)
{
if (!root)
return 0;
int cnt = count_less_than_k(root->left_, k);
if (root->elem_ <= k)
{
cnt++;
cnt += count_less_than_k(root->right_, k);
}
return cnt;
}
int main()
{
tree_node *root = NULL;
for (int i = 1; i< 10; i++)
root = insert(root, i);
for (int i = 0; i < 10; i++)
std::cout << "less than " << i << " cnt: " << count_less_than_k(root, i) << std::endl;
return 0;
}
[coderchen@self c++]$ ./a.out
1 2 3 4 5 6 7 8 9
less than 0 cnt: 0
less than 1 cnt: 1
less than 2 cnt: 2
less than 3 cnt: 3
less than 4 cnt: 4
less than 5 cnt: 5
less than 6 cnt: 6
less than 7 cnt: 7
less than 8 cnt: 8
less than 9 cnt: 9
