Schreibe die Implementierung der FunktionT ComputeMedian() const berechnet den Medianwert im Baum in O (n) Zeit. Nehmen Sie an, dass der Baum eine BST ist, aber nicht unbedingt ausgeglichen ist. Es sei daran erinnert, dass der Median von n Zahlen wie folgt definiert ist: Wenn n ungerade ist, ist der Median x, sodass die Anzahl der Werte kleiner als x gleich der Anzahl der Werte größer als x ist. Wenn n gerade ist, ist eins plus die Anzahl der Werte kleiner als x gleich der Anzahl der Werte größer als x. Bei den Zahlen 8, 7, 2, 5, 9 ist der Median beispielsweise 7, da es zwei Werte gibt, die kleiner als 7 sind, und zwei Werte, die größer als 7 sind. Wenn wir der Menge die Zahl 3 hinzufügen, wird der Median 5.

Hier ist die Klasse des binären Suchbaumknotens:

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

Binäre Suchbaumklasse:

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

};

Ich weiß, ich sollte zuerst die Knoten des Baums zählen und dann einen Inorder Traversal durchführen, bis ich den (n / 2) -ten Knoten erreiche und ihn zurückgebe. Ich habe nur keine Ahnung wie.