inorder traversée d'un arbre B (c ++)

Question

Je travaille sur un b-arbre (ou est-ce BTree?) Pour une classe que je prends en cours. J'ai la plus grande partie correctement mettre en œuvre (je pense). Cependant, je vais avoir du mal à clouer vers le bas un parcours infixe. Voici ma fonction principale:

Tree<char, 5>* tree = new Tree<char, 5>();

char entries[] = {'a', 'g', 'f', 'b', 'k', 'd', 'h', 'm', 'j', 'e', 's', 
                  'i', 'r', 'x', 'c', 'l', 'n', 't', 'u', 'p' };

for (int i = 0; i < 20; i++) {
    tree->insert(entries[i]);
    cout << i << ":\t";
    tree->inorder();
    cout << endl;
}

Je suis donc créer un btree 5 voies qui détient les caractères. J'insérer chacun des caractères dans l'arbre, puis montrant le parcours infixe pour chaque itération à des fins de débogage. Ceci est la sortie que je reçois:

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

Dans la quasi-totalité d'entre eux, quelques-uns des caractères sont dupliquées, mais pas toujours entre les insertions, il (me) semble comme données en double devient. Je ne peux pas sembler ne pas donner un sens, mais voici ma méthode infixe:

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

Dans mon implémentation de noeud, le nombre est le nombre de « données » (chaque char) dans l'arborescence. count + 1 serait le nombre de branches se détachent du noeud pour les noeuds non-feuilles. branche est un tableau de la prochaine série inférieure de noeuds, des données est un tableau des caractères.

Voici mon implémentation de noeud:

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

Le tout de ici utilisé pour insérer:

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, je pense que nous sommes dans la même classe. Je viens de terminer le mien, et j'ai vu le problème dans votre parcours infixe, avec le nouveau aussi. Dans ce deuxième cas:

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

il le fait pour l'ordre, non pas pour la quantité de données est actuellement dans le nœud, il va cracher que de plus petit peu. Je l'ai changé à i<current->data et maintenant il fonctionne très bien. ^^ b vient de terminer. Si cela ne fonctionne pas pour vous, désolé. ^^;

Answer 2

Votre problème est que votre boucle for va de 0 à compter (inclus), mais votre tableau Node :: données ne sont pas définies à données [count] sa seule définies jusqu'à des données [count-1] de sorte que la dernière itération de cette boucle votre obtient toujours des déchets qui pourrait parfois être non nulle et ne pas montrer, mais othertimes peut-être des caractères aléatoires.

Vous devez cas particulier votre code lorsque « i == ordre » comme si

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