小编Nat*_*oub的帖子

编写T ComputeMedian() const在O(n)时间内计算树中值的函数的实现.假设树是BST但不一定是平衡的.回想一下n个数的中值定义如下:如果n是奇数,则中值是x,使得小于x的值的数量等于大于x的值的数量.如果n是偶数,则一加上小于x的值的数量等于大于x的值的数量.例如,给定数字8,7,2,5,9,中位数为7,因为有两个小于7的值和两个大于7的值.如果我们将3加到集合中,则中位数变为5.

这是二叉搜索树节点的类:

template <class T>
class BSTNode
{
public:
BSTNode(T& val, BSTNode* left, BSTNode* right);
~BSTNode();
T GetVal();
BSTNode* GetLeft();
BSTNode* GetRight();

private:
T val;
BSTNode* left;
BSTNode* right;  
BSTNode* parent; //ONLY INSERT IS READY TO UPDATE THIS MEMBER DATA
int depth, height;
friend class BST<T>;
};

二进制搜索树类:

template <class T>
class BST
{
public:
BST();
~BST();

bool Search(T& val);
bool Search(T& val, BSTNode<T>* node);
void Insert(T& val);
bool DeleteNode(T& val);

void BFT(void);
void PreorderDFT(void);
void …