Binäre Suche Bäume C++

Question

Ich habe versucht, eine einfache binäre Suchbaum für die Praxis zu implementieren. Ich habe versucht, nur Werte hinzuzufügen und die Werte in den Knoten zu drucken. Ich bekomme jedoch nicht die richtige aufsteigende Reihenfolge der Werte in den Knoten. Hier ist, was ich habe:

struct Node 
{ 
    int data; 
    Node* leftN; 
    Node* rightN; 

}; 

typedef Node* Node_ptr; 
Node_ptr head; 

//INSERT_VALUE FUNCTION 
Node* insert_value(Node_ptr leaf, int key) 
{ 
    //Root case when there is no set value yet 
    if(leaf == NULL) 
    { 
     leaf = new Node; 
     head = leaf; 
     cout << "Make the first node" << endl; 
     leaf->data = key; 
     leaf->leftN = NULL; 
     leaf->rightN = NULL; 
     return leaf; 
    } 
    //Left child Node 
    if(key < leaf->data) 
    { 
     //Search for a spot in the tree to add a Node (left value < root value < right value) 
     //This is only true for the left child Node 
     if(leaf->leftN != NULL) 
      insert_value(leaf, key); 
     //We have found a spot in the tree to add a new Node and add the value of key 
     else 
     { 
      cout << "Insert-left" << endl; 
      leaf->leftN = new Node; 
      leaf = leaf->leftN; 
      leaf->data = key; 
      leaf->leftN = NULL; 
      leaf->rightN = NULL; 
      return leaf; 
     } 
    } 

    //Right child Node 
    else if(key >= leaf->data) 
    { 
     //Search for a spot to add a new Node in the tree (only amongst the right child Nodes) 
     if(leaf->rightN != NULL) 
      insert_value(leaf, key);  
     //Once we have found a spot to add a new Node, append the new Node 
     else 
     { 
      cout << "Insert-right" << endl; 
      leaf->rightN = new Node; 
      leaf = leaf->rightN;  
      leaf->data = key; 
      leaf->leftN = NULL; 
      leaf->rightN = NULL; 
      return leaf; 
     } 
    } 
} 

//PRINT FUNCTION 
void printTree(Node_ptr leaf) 
{ 
    if(leaf == NULL) 
     return; 
    printTree(leaf->leftN); 
    cout << "Data element: " << leaf->data << endl; 
    printTree(leaf->rightN); 
} 

//MAIN 
int main() 
{ 
    Node_ptr root = NULL; 
    int i; 

    //initialize values 
    for(i = 1; i < 12; i+=2) 
     root = insert_value(root, i); 
    root = head; 
    for(i = 0; i < 11; i+=2) 
     root = insert_value(root, i); 
    root = head; 
    printTree(root); 

    root = head; 
    cout << "Head Node: " << root->data << endl; 

    return 0; 
} 

Wenn ich die Ergebnisse gedruckt, das ist, was ich habe: 0, 2, 4, 6, 8, 10, 1, 3, 5, 7, 9, 11 und der Wert des Kopfknotens ist 1

Answer 1

Da Sie die Einfügung als anrufen:

root = insert_value(root, i); 

der Stelle, an der Sie einfügen wird immer mit Teilbaum beginnend bei der letzten Insertion. Außer der Zeit, zu der Sie die ungeraden Zahlen neu eingeben, wenn Sie mit dem Einfügen beginnen.

Wenn erstellen Sie ein class BinarySearchTree, die einen Kopfzeiger enthält, und eine Insert-Methode ein int value nehmen, die Node::insert(head, value) ruft, dann können Sie nur auf dieser Klasse Einsatz nennen, ohne sie einen Knoten vorbei, und es kann immer dafür sorgen, dass Die Einfügungen verwenden die Wurzel des Baums für den Beginn der Rekursion.

Nur ich, aber ich hätte einen Konstruktor für Knoten, der eine int und initialisiert die Zeiger auf NULL. Auf diese Weise müssen Sie dies bei der Einfügemethode nicht tun.

Answer 2

Im Blatt-> Knoten? ! = NULL Fall denke ich, statt

des Aufrufs

insert_value(leaf, key); 

Sie

leaf->node? = insert_value(leaf->node?, key) 

wo sagen wollen? ist natürlich entweder L oder R.

Etwas, das Sie sich anschauen sollten einen Kommentar zu der Methode ist das Hinzufügen wie so:

// Adds the given key to the (sub-)tree rooted at node* then returns the new root 
// of that (sub-)tree. 
node *insert_value_and_return_root(node *root, int value) { ... }