finde transversal de un árbol B (c ++)

Question

Estoy trabajando en un árbol B (o es BTree?) Para una clase que estoy tomando actual. Tengo la mayor parte de ella implementar correctamente (creo). Sin embargo, estoy teniendo problemas para clavar abajo de un recorrido en orden. Aquí está mi función principal:

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

Así que estoy crear un árbolB 5 vías que contiene caracteres. Estoy insertando cada uno de los caracteres en el árbol, y luego muestra el recorrido en orden para cada iteración para fines de depuración. Esta es la salida me sale:

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

En casi todos ellos, algunos de los caracteres están duplicados, pero no de manera consistente entre las inserciones, por lo que (para mí) no parece que los datos duplicados está recibiendo. Me parece que no puede hacer sentido de ella, pero aquí está mi método finde:

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

En mi implementación del nodo, el recuento es el número de datos '' (cada uno carbón de leña) en el árbol. count + 1 sería el número de ramas desprende del nodo para los nodos que no son hojas. rama es una matriz de la siguiente serie inferior de los nodos, los datos es una matriz de los caracteres.

Aquí está mi implementación del nodo:

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

Aquí todo de utilizar para insertar:

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

Je, creo que estamos en la misma clase. Me acaba de terminar la mía, y vi el problema en su recorrido en orden, con el nuevo también. En ese segundo si:

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

lo hace el pedido, no por la cantidad de datos se encuentra actualmente en el nodo, así que va a escupir que poco más bits. Lo cambié a i<current->data y ahora funciona muy bien. ^^ b acaba de terminar. Si esto no funciona para usted, lo siento. ^^;

Answer 2

Su problema es que su ciclo for va de 0 a contar (ambos inclusive), pero su Nodo :: matriz de datos no está definida en los datos de recuento [] su único definidos hasta el recuento de datos [1] por lo que la última iteración de su bucle que siempre se sale con la basura que a veces podría ser distinto de cero y no se presenta, pero othertimes podría ser caracteres aleatorios.

Es necesario caso especial su código para cuando "i == orden" como tal

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