2016-11-02 7 views
1

Ich versuche, einen binären Baum (kein binärer Suchbaum) zu implementieren. Es wird hauptsächlich eine Klassenvorlage sein, die aus Einfügen/Löschen/Suchen & klare Prozeduren besteht. Die in den Knoten enthaltenen Daten könnten alles sein. So etwas wie unten:Benötigen Sie Hilfe zu Binärbaum-Prozeduren (NICHT binäre Suchbaum)

template<class T> 
class BinaryTree 
{ 
public: 
    BinaryTree(int size); 
    ~BinaryTree(); 
    virtual bool insert(T data); 
    virtual bool remove(T data); 
    virtual void clear(); 
    virtual bool search(T data); 
    virtual void display(std::string str, ETravType type); 
    virtual unsigned int getSize(); 
    //friend void swapWithLastNode(Node *root, Node **nodeToRemove); 
protected: 
    virtual void inorder(Node<T>* root); 
    virtual void preorder(Node<T>* root); 
    virtual void postorder(Node<T>* root); 
    virtual void removeAll(Node<T>* root); 
    Node<T>* root; 
    int max; 
    unsigned int curSize; 
}; 

Ich brauche Hilfe auf den Algorithmen, vorzugsweise iterative (wollen rekursiv zu vermeiden, durch Größenbeschränkungen zu stapeln), zum Einsatz verwenden, suchen & löschen:

  • Einfügen: Wie stellt man sicher, dass der Baum nicht links/rechts schief wird?

  • Löschen: Was ist der beste Weg zum Löschen, wenn der Knoten die beiden untergeordneten Elemente enthält (Beispiel: In BST ersetzen Sie durch Inorder-Nachfolger).

  • Suche: Gibt es einen effizienten Weg, um eine O (n) Suche zu verhindern?

Es gibt eine Fülle von Ressourcen im Internet für BST Verfahren (meist rekursiv), aber kein für Binary Tree (oder zumindest ich war nicht in der Lage, etwas zu finden). Daher dachte ich, es hier zu posten.

+0

Ihre Fragen zu einfügen und löschen scheinen mir zu zeigen, dass Sie nicht über die Positionen der Knoten im Baum und an diesem Punkt, den ich zu fragen, warum brauchen Pflege werden Sie sogar einen binären Baum statt mit von nur einer einfach verknüpften Liste? – PeterT

Antwort

4

Es gibt einen echten Grund, BST gegenüber BT zu bevorzugen.

BST ist log(N) zum Einfügen, Löschen und Suchen, während BT am Ende mit vollständiger Traversierung des Baums auf Kosten von O(N) enden kann.

  1. Einfügen: Wie wird sichergestellt, dass der Baum nicht links/rechts schief wird?

    Ich fürchte, dass nichtmachen würde jeden Unterschied zur Gesamtleistung des Baumes. Wenn Sie das noch tun möchten, erfahren Sie mehr über self-balancing tree.

  2. Löschen: Was ist der beste Weg zum Löschen, wenn der Knoten die beiden untergeordneten Elemente enthält (Beispiel: In BST ersetzen Sie durch Inorder-Nachfolger).

    Zum Löschen einfach einen beliebigen Blattknoten des Baums auswählen und an dieser Position ersetzen. Der Binärbaum hat kein Muster, also würde die Auswahl eines zufälligen Knotens keinen Unterschied machen. Also, kein Problem bei der Aufnahme von Blattknoten.

  3. Suche: Gibt es einen effizienten Weg, um eine O (n) Suche zu verhindern?

    Nein, es gibt keinen besseren Weg zu verhindern O(n) Suche. Sie müssen den gesamten Baum durchlaufen, es gibt kein Muster/keine Reihenfolge von Knoten in BT, um Ihnen bei der effizienten Navigation zu helfen.