#include <iostream>
#include <stdio.h>
using namespace std;
/*
问题：假设你正在读取一串整数。每隔一段时间，你希望找出数字x的秩（小于或等于x的值的数目）。请实现
数据结构和算法支持这些操作。也就是说，实现track(int x)方法，每读入一个数字都会调用该方法；以及
getRankOfNumber(int x)方法，返回值为小于或等于x的元素个数(不包括x本身)。
分析:
针对问题1： track(int x)这个很容易实现，直接每次读取后与x进行比较，如果<=x，那么就累加秩的数量
针对问题2： getRankOfNumber(int x)，我猜想，可以用排序实现啊，然后二分查找中的lowwerBound，
lowwerBound是返回等于x的第一个数，或者第一个大于x的下标，将lowwerBound得到的数减去1
即为所求
输入:
8(8个结点) 24（查找的元素）
20 15 25 10 23 5 13 24
8 29
20 15 25 10 23 5 13 24
输出:
6
-1
关键:
1书上解法：题目讲的这么隐晦，其实就是二叉查找树，所谓的track就是插入方法，所谓的getRangOfNumber就
是统计小于x的数目。时间复杂度为O(logN)
最关键的部分修改二叉查找树的部分中为结点添加其左孩子个数这样一个属性，
那么发现：统计的时候发现,当前查找值=结点值，就返回结点的左孩子个数；
< ,就查找左子树，如果左子树为空，返回-1，否则递归处理左子树
> ,就查找右子树，右子树为空，返回-1；递归计算右子树的排名值，如果为-1，直接返回-1；
不为-1，就将当前结点左孩子个数+当前节点本身1个+右子树的个数 累加返回
2 本题的难点在于如何统计一颗树的左子树中元素个数
生成每个结点的左子树个数，每个结点C的左子树中元素个数 = 结点C的左孩子的所有结点个数 + 1
设当前结点为C,f(C)表示结点C的左子树中所有元素个数 = 结点C的左孩子的 左子树的所有元素个数 + 1(左孩子本身) + 结点C的左孩子的右子树中所有元素个数 + 结点C的左孩子的右孩子
f(C) = f(C->left) + 1 + g(C->left->right) + 1
设g(C)是结点C包含的所有子孙结点
g(C) = g(C->left) + g(C->right) + 2(如果左右孩子结点都存在，只有1个存在就是1，都不存在就是0)
因此，我所使用的方式是：先统计树中每颗树的子孙节点个数，然后第二遍再计算左子树中元素个数
//获取左孩子个数,f(C) = f(C->left) + 1 + g(C->left->right) + 1,f(C)表示结点C的左子树中所有元素个数,g(C)是结点C包含的所有子孙结点
//但这样只把根节点及其左子树遍历到了右子树没有处理
int getLeftChildsNum(TreeNode* head)
{
if(NULL == head)
{
return 0;
}
if(head->_pLeft)
{
int num = getLeftChildsNum(head->_pLeft) + 1 ;
if(head->_pLeft->_pRight)
{
//加上左孩子的右孩子的所有结点和其本身结点
num += head->_pLeft->_pRight->_totalSize + 1;
}
head->_leftSize = num;
}
//没有左孩子，返回0
else
{
head->_leftSize = 0;
}
//神之一手，右子树需要遍历处理，但是其结果不返回
if(head->_pRight)
{
getLeftChildsNum(head->_pRight) ;
}
return head->_leftSize;
}
*/
typedef struct TreeNode
{
TreeNode():_leftSize(-1),_totalSize(-1){}
int _value;
TreeNode* _pLeft ;
TreeNode* _pRight;
int _leftSize;//左孩子个数
int _totalSize;//所有子孙结点个数
}TreeNode;
int gIndex = 0;
const int MAXSIZE = 10000;
TreeNode gTreeNodeArray[MAXSIZE];
TreeNode* createTreeNode()
{
++gIndex;
gTreeNodeArray[gIndex]._pLeft = gTreeNodeArray[gIndex]._pRight = NULL;
return & gTreeNodeArray[gIndex];
}
//二叉查找树
class BinarySearchTree
{
public:
BinarySearchTree(){}
//析构时要释放所有结点
~BinarySearchTree(){}
void generateLeftNum()
{
getChildsNum(_head);
getLeftChildsNum(_head);
}
//将当前结点插入到树中，并更新结点的左子树结点值，默认每个结点的左子树结点值为0
void insertNode(TreeNode* node , TreeNode* head)
{
if(NULL == node || NULL == head)
{
return ;
}
//插入左子树
if(node->_value <= head->_value)
{
if(head->_pLeft)
{
//返回当前结点的左孩子的个数
insertNode(node ,head->_pLeft);
}
else
{
head->_pLeft = node;
}
}
//将结点插入到根节点的右子树上
else
{
if(head->_pRight)
{
insertNode(node , head->_pRight);
}
else
{
head->_pRight = node;
}
}
}
//统计在二叉查找树中共有多少个结点小于value
int getRank(int value , TreeNode* head)
{
if(NULL == head)
{
return -1;
}
//如果等于根节点，就返回根节点的左孩子个数
if(value == head->_value)
{
return head->_leftSize;
}
//如果在树的左侧，对左孩子递归调用
else if(value < head->_value )
{
//如果左子树为空，直接返回-1
if(NULL == head->_pLeft)
{
return -1;
}
else
{
return getRank(value , head->_pLeft);
}
}
//如果在树的右侧，需要加上当前结点左子树中结点个数+当前结点本身1个+当前结点右子树中统计的值
else
{
if(NULL == head->_pRight)
{
return -1;
}
int num = getRank(value ,head->_pRight);
//说明没有查找到
if(-1 == num)
{
return -1;
}
return (head->_leftSize + 1 + num);
}
}
TreeNode* _head;
private:
/*
生成每个结点的左子树个数，每个结点C的左子树中元素个数 = 结点C的左孩子的所有结点个数 + 1
设当前结点为C,f(C)表示结点C的左子树中所有元素个数 = 结点C的左孩子的 左子树的所有元素个数 + 1(左孩子本身) + 结点C的左孩子的右子树中所有元素个数
f
f(C) = f(C->left) + 1 + g(C->left->right)
设g(C)是结点C包含的所有子孙结点
g(C) = g(C->left) + g(C->right) + 2(如果左右孩子结点都存在，只有1个存在就是1，都不存在就是0)
*/
int getChildsNum(TreeNode* head)
{
if(NULL == head)
{
return 0;
}
else
{
int leftNum = 0;
int rightNum = 0;
int totalNum = 0;
if(head->_pLeft)
{
leftNum = getChildsNum(head->_pLeft);
totalNum += 1 + leftNum;
}
if(head->_pRight)
{
rightNum = getChildsNum(head->_pRight);
totalNum += 1 + rightNum;
}
head->_totalSize = totalNum;
return head->_totalSize;
}
}
//获取左孩子个数,f(C) = f(C->left) + 1 + g(C->left->right) + 1,f(C)表示结点C的左子树中所有元素个数,g(C)是结点C包含的所有子孙结点
//但这样只把根节点及其左子树遍历到了右子树没有处理
int getLeftChildsNum(TreeNode* head)
{
if(NULL == head)
{
return 0;
}
if(head->_pLeft)
{
int num = getLeftChildsNum(head->_pLeft) + 1 ;
if(head->_pLeft->_pRight)
{
//加上左孩子的右孩子的所有结点和其本身结点
num += head->_pLeft->_pRight->_totalSize + 1;
}
head->_leftSize = num;
}
//没有左孩子，返回0
else
{
head->_leftSize = 0;
}
//神之一手，右子树需要遍历处理，但是其结果不返回
if(head->_pRight)
{
getLeftChildsNum(head->_pRight) ;
}
return head->_leftSize;
}
};
void process()
{
int nodeNum;
int searchValue;
while(cin >> nodeNum >> searchValue)
{
if(nodeNum < 1)
{
continue;
}
//下面创建结点，第一个结点为根节点
TreeNode* head;
BinarySearchTree tree;
for(int i = 0 ; i < nodeNum ; i++)
{
TreeNode* node = createTreeNode();
cin >> node->_value;
if(!i)
{
head = node;
tree._head = head;
}
//根节点初始化以后，才能插入结点
else
{
//插入结点
tree.insertNode(node , tree._head);
}
}
tree.generateLeftNum();
//获取当前给定值的排名
int rank = tree.getRank(searchValue , tree._head);
cout << rank << endl;
}
}
int main(int argc, char* argv[])
{
process();
getchar();
return 0;
}
| 
转播
