inorder Bツリーのトラバーサル（C++）

Question

私は現在取り組んでいるクラスのBツリー（またはそれはBTreeですか？）に取り組んでいます。私はそれのほとんどを正しく実装している（私は思う）。しかし、私はインオーダートラバーサルを釘付けにするのに問題があります。ここに私の主な機能は次のとおりです。

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

私は5文字のbtreeを作成しています。私はツリーにそれぞれの文字を挿入し、デバッグの目的で各反復のインオーダートラバーサルを表示しています。これは私が手出力される：重複データがでてきているように（私には）文字の一部が複製され、ほぼすべてのそれらの中

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 

をではなく、一貫して、挿入の間に、それはいないようです。私はそれの意味をなすように見えることはできませんが、ここで私のINORDER方法です：

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

私のノードの実装では、カウントは、ツリーに「データ」の数（各文字）です。 count + 1は、非リーフノードのノードからいくつのブランチが離れるかです。 branchはノードの次の下位集合の配列、dataは文字の配列です。

は、ここに私のノードの実装です：

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

へぇようなとき、「私==オーダー」のためのあなたのコードが必要

は、私たちは、同じクラスにしていると思います。私はちょうど私のことを終えました。あなたのインオーダートラバーサルで問題を、新しいものでも見ました。もし、第2の場合：

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

それは順序のために、ないどのくらいのデータノードに現在あるので、少し余分なことを吐き出すために起こっているためにそれを行います。私はそれをi<current->dataに変更しましたが、今はうまく動作します。 ^^ bちょうど終わった。それがあなたのために働かないならば、申し訳ありません。 ^^;

Answer 2

あなたの問題は、あなたがforループ（包括的）カウントするように0から起こっているということですが、あなたのノード：

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

ここで挿入するために使用し、すべてです。 ：データ配列はデータ[count]で定義されておらず、データ[count-1]までしか定義されていないので、そのループの最後の反復は常にガベージを取得し、時には非ゼロで表示されませんランダムな文字。あなたは特別なケースにそう

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