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

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。

这里是二叉搜索树节点的class：

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>;
};

二叉搜索树class:

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) 个节点和 return 它。我只是不知道如何。

Answer 1

正如你所说，首先找到节点的数量是相当容易的，进行任何遍历：

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

然后，当节点号为 n/2:

时中止的中序遍历

// index is a global variable / class variable, or any other variable that is constant between all calls
index=0
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个节点，当然对i==n/2也是如此，当你找到它的时候是第n/2个节点，你return它。

作为旁注，您可以向 BST 添加功能以有效地找到第 i 个元素（O(h)，其中 h 是树的高度），使用 order statistics trees.

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

Find median in binary search tree

algorithm

tree

median

binary-search-tree