Schreiben Sie die Implementierung der Funktion T ComputeMedian() const
, die den Medianwert im Baum in O (n) Zeit berechnet. Angenommen, der Baum ist ein BST, ist aber nicht unbedingt ausgewogen. Erinnern wir uns, dass der Median von n Zahlen wie folgt definiert ist: Wenn n ungerade ist, ist der Median x, so dass 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, weil zwei Werte kleiner als 7 und zwei Werte größer als 7 sind. Wenn wir der Menge Nummer 3 hinzufügen, wird der Median 5. HierSuchen Sie den Median im binären Suchbaum
ist die Klasse von binären Suchbaum Knoten:
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 Suchbaum Klasse:
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 die Knoten des Baumes zuerst zählen und dann ein inorder Traversal tun bis ich den (n/2) ten Knoten erreiche und ihn zurückgebe. Ich habe nur keine Ahnung wie.
Im Fall einer Liste müssen Sie Zeiger an beiden Enden beginnen und nach innen arbeiten, um den Median zu finden. Da Ihr Baum jedoch nicht ausgeglichen ist, reduziert sich der Worst Case auf eine verkettete Liste. Daher können Sie nicht vermeiden, genau das gleiche zu tun. Beginne Zeiger mit den Min- und Max-Werten und berechne abwechselnd Inorder-Nachfolger (Min) und Inorder-Vorgänger (Max), bis die Werte gleich sind. – BadZen
@BadZen Ich bin mit dem "inorder-Vorgänger" nicht ganz vertraut .. Könnten Sie bitte weiter erklären? –
Next() und Prev() Baumwerte. – BadZen