在二进制搜索树中查找中位数

一尘不染

在二进制搜索树中查找中位数

algorithm

编写函数的实现，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）个节点并返回它。我只是不知道如何。

阅读 318

2020-07-28

共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第一个节点按顺序是第一个节点，这当然也适用于i==n/2，当您发现它是n/2第一个节点时，您将其返回。

附带说明一下，您可以使用订单统计信息树将功能添加到BST中，以i有效地找到元素（O(h)，这h是树的高度）。

2020-07-28