Inorder Traversal eines B-Baumes (C++)

Question

Ich arbeite an einem B-Baum (oder ist es BTree?) Für eine Klasse, die ich derzeit nehme. Ich habe das meiste davon richtig umgesetzt (glaube ich). Allerdings habe ich Probleme, eine Inorder-Traversierung zu finden. Hier ist meine Hauptfunktion:

Also ich bin ein 5-Wege-Baum, der Zeichen enthält. Ich füge jeden der Zeichen in den Baum ein und zeige dann den Invers-Durchlauf für jede Iteration zu Debugging-Zwecken an. Dies ist die Ausgabe erhalte ich:

0: a 
1: ag 
2: afg 
3: abfg 
4: abffgk 
5: abdgfgk 
6: abdgfghk 
7: abdgfghkm 
8: abdgfghjjkm 
9: abdefghjjkm 
10: abdefghjjkms 
11: abdefghimjkms 
12: abdefghimjkmrs 
13: abdefghimjkmrrsx 
14: abccdefghimjkmrrsx 
15: abccdefghimjklmsrsx 
16: abccdefghimjklmnrsx 
17: abccdefghimjklmnrstx 
18: abccdefghimjklmnrstux 
19: abccdefghimjjklmmnprstux 

In fast alle von ihnen, einige der Zeichen dupliziert werden, aber nicht konsequent zwischen Einfügungen, so ist es (für mich) scheint nicht, wie doppelte Daten zu bekommen. ich kann nicht Sinn zu machen scheinen, aber hier ist meine inorder Methode:

template <class Record, int order> 
void Tree<Record, order>::inorder() 
{ 
    inorder(root); 
} 

template <class Record, int order> 
void Tree<Record, order>::inorder(Node<Record, order> *current) 
{ 
    for (int i = 0; i < current->count+1; i++) { 
     if (current->branch[i]) 
      inorder(current->branch[i]); 
     if (i < order-1 && current->data[i]) 
      cout << current->data[i]; 
    } 
} 

in meinem Knoten Implementierung Zahl ist die Anzahl von ‚Daten‘ (jedes Zeichen) im Baum. count + 1 wäre, wie viele Zweige aus dem Knoten für die Nicht-Blattknoten kommen. branch ist ein Array des nächstniedrigeren Knotensatzes, data ist ein Array der chars.

Hier ist meine Knoten Implementierung:

template <class Record, int order> 
struct Node 
{ 
    int count; 
    Record data[order - 1]; 
    Node<Record, order>* branch[order]; 
    Node() : count(0) {} 
}; 

Hier ist alles verwendet, einfügen:

template <class Record, int order> 
ErrorCode Tree<Record, order>::insert(const Record& new_entry) 
{ 
    Record median; 
    Node<Record, order> *right_branch, *new_root; 
    ErrorCode result = push_down(root, new_entry, median, right_branch); 

    if (result == overflow) { 
     new_root = new Node<Record, order>(); 
     new_root->count = 1; 
     new_root->data[0] = median; 
     new_root->branch[0] = root; 
     new_root->branch[1] = right_branch; 
     root = new_root; 
     result = success; 
    } 

    return result; 
} 

template <class Record, int order> 
ErrorCode Tree<Record, order>::push_down(
       Node<Record, order> *current, 
       const Record &new_entry, 
       Record &median, 
       Node<Record, order> *&right_branch) 
{ 
    ErrorCode result; 
    int position; 

    if (current == NULL) { 
     median = new_entry; 
     right_branch = NULL; 
     result = overflow; 
    } 
    else { 
     if (search_node(current, new_entry, position) == success) 
      result = duplicate_error; 
     else { 
      Record extra_entry; 
      Node<Record, order> *extra_branch; 
      result = push_down(current->branch[position], new_entry, 
           extra_entry, extra_branch); 
      if (result == overflow) { 
       if (current->count < order - 1) { 
        result = success; 
        push_in(current, extra_entry, extra_branch, position); 
       } 
       else 
        split_node(current, extra_entry, extra_branch, position, 
           right_branch, median); 
      } 
     } 
    } 

    return result; 
} 

template <class Record, int order> 
void Tree<Record, order>::push_in(Node<Record, order> *current, 
       const Record &entry, 
       Node<Record, order> *right_branch, 
       int position) 
{ 
    for (int i = current->count; i > position; i--) { 
     current->data[i] = current->data[i-1]; 
     current->branch[i+1] = current->branch[i]; 
    } 

    current->data[position] = entry; 
    current->branch[position+1] = right_branch; 
    current->count++; 
} 

Answer 1

Heh, ich denke, dass wir in der gleichen Klasse sind. Ich habe gerade meins beendet, und ich sah das Problem in Ihrem Inorder Traversal, auch mit dem Neuen. In diesem zweiten, wenn:

if (i < order-1 && current->data[i]) 
cout << current->data[i]; 

es tut es für den Auftrag, nicht, wie viele Daten zur Zeit im Knoten, so, es wird ein gewisses Extra auszuspucken. Ich habe es in i<current->data geändert und jetzt funktioniert es gut. ^^ b Gerade fertig. Wenn es für dich nicht funktioniert, sorry. ^^;

Answer 2

Ihr Problem ist, dass Ihre for-Schleife von 0 wird zählen (einschließlich), aber Ihr Knoten: : Daten-Array ist nicht definiert bei Daten [count] es ist nur bis zu Daten [count-1] definiert, so dass die letzte Iteration Ihrer Schleife immer Müll bekommt, der manchmal nicht Null ist und nicht angezeigt wird, aber manchmal auch mal zufällige Zeichen.

Sie müssen Sonderfall Code für, wenn "i == Ordnung" wie so

if (current->branch[i]) 
    inorder(current->branch[i]); 
if (i < order-1 && current->data[i]) 
    cout << current->data[i];