查找中位数二叉搜索树 [英] Find median in binary search tree
问题描述
编写函数 T ComputeMedian()const的
,计算树的中值在O(n)的时间执行。假设树是BST但不一定平衡。回想一下,n个数字中值的定义如下:如果n是奇数,中位数为x使得值小于x的数目等于值大于x的数。如果n是偶数,则一加值小于x的数目等于值大于x的数。例如,给定的号码8,7,2,5,9,中位数为7,因为有两个值小于7和大于7的两个值如果再加号3到集,中值变为5。
Write the implementation of the function T ComputeMedian() const
that computes the median value in the tree in O(n) time. Assume that the tree is a BST but is not necessarily balanced. Recall that the median of n numbers is defined as follows: If n is odd, the median is x such that the number of values smaller than x is equal to the number of values greater than x. If n is even, then one plus the number of values smaller than x is equal to the number of values greater than x. For example, given the numbers 8, 7, 2, 5, 9, the median is 7, because there are two values smaller than 7 and two values larger than 7. If we add number 3 to the set, the median becomes 5.
下面是类的二叉搜索树节点:
Here is the class of binary search tree node:
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>;
};
二叉搜索树类:
Binary search tree 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)个节点,并将其返回。我只是不知道如何。
I know I should count the nodes of the tree first and then do an inorder traversal until I reach (n/2)th node and return it. I just have no clue how.
推荐答案
正如你提到的,这是很容易先找到节点的数量,做任何遍历:
As you mentioned, it is fairly easy to first find the number of nodes, doing any traversal:
findNumNodes(node):
if node == null:
return 0
return findNumNodes(node.left) + findNumNodes(node.right) + 1
然后,一个序遍历的终止当节点数量为n / 2
Then, with an inorder traversal that aborts when the node number is 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,在我
日您处理节点,是我
次才能节点,这当然也适用于我== N / 2
,当你发现它是 N / 2
个节点,你回吧。
The idea is that in-order traversal processes nodes in BST in sorted manner. So, since the tree is a BST, the i
th node you process, is the i
th node in order, this is of course also true for i==n/2
, and when you find it is the n/2
th node, you return it.
作为一个方面说明,您可以添加功能,BST找到我
个元素有效( 0(H)
,其中 ^ h
是树的高度),使用订单统计树木的。
As a side note, you can add functionality to BST to find i
th element efficiently (O(h)
, where h
is the tree's height), using order statistics trees.
这篇关于查找中位数二叉搜索树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!