在二叉搜索树中查找中位数

Question

编写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 PreorderDFT(BSTNode<T>* node);
void PostorderDFT(BSTNode<T>* node);
void InorderDFT(BSTNode<T>* node);
void ComputeNodeDepths(void);
void ComputeNodeHeights(void);
bool IsEmpty(void);
void Visit(BSTNode<T>* node);
void Clear(void);

private:
BSTNode<T> *root;
int depth;
int count;
BSTNode<T> *med; // I've added this member data.

void DelSingle(BSTNode<T>*& ptr);
void DelDoubleByCopying(BSTNode<T>* node);
void ComputeDepth(BSTNode<T>* node, BSTNode<T>* parent);
void ComputeHeight(BSTNode<T>* node);
void Clear(BSTNode<T>* node);

};

我知道我应该首先计算树的节点然后进行顺序遍历,直到我到达第(n/2)个节点并返回它.我不知道怎么回事.

Answer 1

正如您所提到的,首先找到节点数量,进行任何遍历都相当容易:

findNumNodes(node):
   if node == null:
       return 0
   return findNumNodes(node.left) + findNumNodes(node.right) + 1

然后,当节点数为n/2时,中断遍历将中止:

index=0 //id is a global variable / class variable, or any other variable that is constant between all calls
findMedian(node):
   if node == null:
       return null
   cand = findMedian(node.left)
   if cand != null:
        return cand
   if index == n/2:
       return node
   index = index + 1
   return findMedian(node.right)

这个想法是按顺序遍历以有序的方式处理BST中的节点.因此,由于树是BST,i您处理的i第th个节点是顺序的第th个节点,当然也是如此i==n/2,当您发现它是第n/2th个节点时,您将其返回.

作为旁注,您可以使用订单统计树向BST添加功能以i有效地找到元素(树的高度O(h)在哪里h).