2

現在受講しているクラスの 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

それらのほとんどすべてで、一部の文字が重複していますが、挿入間で一貫していないため、（私には）重複データが入っているようには見えません。意味がわからないようですが、ここに私の順不同の方法:

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>
struct Node
{
    int count;
    Record data[order - 1];
    Node<Record, order>* branch[order];
    Node() : count(0) {}
};

挿入に使用されるものはすべて次のとおりです。

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

2 に答える 2

1

へー、同じクラスだと思います。私はちょうど私のものを終えました、そして私はあなたの順序通りのトラバーサルに問題を見ました、新しいものでも。その秒で次の場合:

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

ノードに現在どれだけのデータがあるかではなく、注文のためにそれを行うので、少し余分に吐き出します。に変更したところi<current->data、問題なく動作するようになりました。^^b ちょうど終わったところです。うまくいかない場合は、申し訳ありません。^^;

于 2010-12-03T18:15:18.350 に答える
1

あなたの問題は、for ループが 0 から count (包括的) になることですが、Node::data 配列が data[count] で定義されておらず、data[count-1] までしか定義されていないため、最後の反復がそのループは常にガベージを取得しますが、これはゼロ以外で表示されない場合もあれば、ランダムな文字である場合もあります。

「i == order」のようにコードを特別なケースにする必要があります

if (current->branch[i])
    inorder(current->branch[i]);
if (i < order-1 && current->data[i])
    cout << current->data[i];
于 2010-12-02T04:33:33.163 に答える