BSTree中查找第k小的数

BSTree中查找第k小的数

二叉搜索树中超找第k小元素，要求时间复杂度为O(logn).

分析：要查找第k小的元素，首先得应该知道以当前节点为根的左子树有多少个节点，加入为m个，

如果k = m + 1,很好pcur就是要第k小元素了

如果k < m + 1,那么我们只需要递归在左子树中查找

如果k > m + 1,那么我们就在右子树中查找第k - m - 1小的元素了。

分析到此，可以知道每当遍历到一个节点，必须知道子树个数信息，不然不知道往哪个分支走，第一反应是在

节点中增加一个field，即表示节点个数信息，那加入题目不让你添加额外的空间怎么办？

继续分析，要想找到第k小的元素，我们就利用中序遍历（从小到大），先从最小元素往后遍历不就行了，记录走了多少步了

如果到k步了，停止return就ok了，至此代码很容易就写出来了：

/*
*@brief 寻找第k小元素
*@param pcur the root of the subtree
*@param k the index of the elements searched for
*@return the node of the kth elements
*@time O(logn)
*/
BTreeNode* BSTree::get_kth_value(BTreeNode* pcur, int &k)
{
if(NULL == pcur)
return NULL;
BTreeNode *rst = NULL;
rst = get_kth_value(pcur->left, k);
--k;
if(0 == k)
rst = pcur;
if(0 < k)
rst = get_kth_value(pcur->right, k);
return rst;
} 转自http://www.cnblogs.com/buptLizer/archive/2012/04/01/2428200.html