1

私と私の友人は、データベース上のクラスに単純なDBMSを実装する必要があります。

DBMSの主要部分はすぐに使用できます。つまり、すべてのコマンド（挿入、削除、更新、選択）が徹底的にテストされており、かなり正常に機能しているようです。

最後の機能では、B +ツリーを実装する必要がありますが、これは私の正直な意見では非常に困難です。

私たちがやろうとしたのは、最初にメインメモリで動作する単純なB +ツリーを実装することです（ファイルベースのバージョンを実装する前に）。B +理論についてオンラインで読み、さまざまな擬似コードを研究した後、再帰的な実装を作成することができました。VS2010のデバッガーを使用してテストしましたが、非常にうまく機能しているようです。

問題は、作成されたツリーをある程度視覚化したいということです。これにより、デバッグが容易になると思います。つまり、実際のツリーを見ることができれば、結果が正しいかどうかを確実に知ることができます。

それで、例えば最も単純なケースを取り上げましょう。B +ツリーのノードに、データとして2つの整数と、子ノードへの3つのポインターがあるとします。

40、50、48、20、57、49の数字を挿入しましょう。次のWebサイトから：http ：//www.seanster.com/BplusTree/BplusTree.html

次のアニメーションが表示されます。

ここに画像の説明を入力してください

矢印を追加しました。

次に、このツリーをC++で次のように印刷します。

          [48|50]
  [20|40] [48|49] [50|57]

しかし、どうすればいいのかわかりません。プレオーダー、ポストオーダー、インオーダーなどのツリートラバーサルについて読んだことがありますが、それらが私が望むことを達成するのに役立つとは思いません。

私が知っているのはルートノードだけです。そのルートノードから、次の方法でツリーをいくらかトラバースする必要があります。

  1. ルートにアクセス
  2. ルートを印刷
  3. ルートの子供たちを訪ねる
  4. 各子の値を出力します
  5. ルートの子ごとに、その子（ルートの孫）にアクセスします。
  6. 孫の値を印刷する
  7. 他の孫にも同じことをします
  8. 同じように孫の子供たちにも同じことをします

この問題に取り組むための最良の方法は何でしょうか？前もって感謝します

4

1 に答える 1

0

レベル順トラバーサルについての私のコメントを拡張します-あなたが正しく質問していることを理解していれば、このようなものが機能するはずです？myNodeとwhatnotが定義されていないため、実際には機能しませんが、うまくいけば、アイデアが示されます。

std::vector<std::vector<std::string> > reprVect;

void visit(myNode n) { 
    if (reprVect.size() < myNode.level)
        reprVect.push_back(std::vector<std::string>());
    }
    reprVect[myNode.level].push_back(myNode.string_repr());
}

// [...]

std::queue<myNode> q;
q.push_back(rootNode);
while (!q.empty()) {
    myNode curNode = q.front();
    q.pop_front();
    visit(q);
    if (curNode.left != NULL) {
        q.push_back(curNode.left);
    } else { /*insert blank into the reprVect */ }
    if (curNode.right != NULL) {
        q.push_back(curNode.right);
    } else { /*insert blank into the reprVect */ }
}

// use cout to print contents of reprVect
于 2012-08-20T15:23:42.633 に答える