1

問題をモデル化するためのツリーデータ構造について読んでいます。ファイルシステムのフォルダ/ファイル表現に非常によく似たデータのメモリ表現を構築する必要があります（ディスクに保存されている実際のファイルではなく、エクスプローラのような構造を意味します）。ツリーの深さは最大10です。中間ノードには中程度の数の子（たとえば10）しかありませんが、数千のリーフノードが存在する可能性があります。[つまり、フォルダー内の数千のファイルとファイルがリーフノードです]

いくつかの考え

  • 1つのノードには最大で2つの子しか持たないため、バイナリツリーは機能しません。（3つのサブフォルダーを持つことができるとしましょう）
  • 私のデータは注文できるので、非常に一般的なツリーの実装は非効率的かもしれません。左の兄弟のように、右の兄弟よりも小さい/小さいです。これにより、効率的なトラバーサルが可能になることを願っています。
  • Bツリーは非常に近いように聞こえますが、バランス要件を主張しています。私の場合、深さは10を超えることはありませんが、必ずしもその深さのすべてのブランチである必要はありません（たとえば、c：/ windows、C：/MyDoc../A/B/C）

あなたの経験を手伝ってください。ツリーまたは適切なデータ構造をカスタムで利用できるようにする必要があります（プログラミング言語に固有のものではありません）。

4

4 に答える 4

3

ファイルとフォルダの2種類のノードがあります。

フォルダノードには子のセット（またはマップ）が含まれ、子自体がファイルまたはフォルダである場合があります。

または、フォルダノードに一連のファイルと一連のフォルダを含めることをお勧めします。

セットには、順序集合のお気に入りの表現（おそらく、使用している言語に付属しているもの）を使用してください。状況の正確な詳細によっては、代わりにマップを使用することをお勧めします。

于 2012-04-20T19:01:06.513 に答える
1

一般的なファイルシステムでは、「ディレクトリツリー」と検索ツリーは同じものではなく、通常は別々に管理されます。「ディレクトリツリー」は、フォルダにあるファイル/サブフォルダ、または特定のファイルへのパスを示し、ユーザーがファイルを整理する方法を反映しているだけで、ユーザーにのみ役立ちます。一方、検索ツリーは、高速検索を容易にするために、すべてのファイルのグローバルインデックスを維持します。

たとえば、Linuxのようなファイルシステムを実装できます。この場合、フォルダーは、フォルダーに含まれる他のファイル/フォルダーのポインターを記録するファイルです。同時に、すべてのファイルポインタをリーフとして持つB+ツリーを維持します。B +ツリーのバランス状態は、ユーザーがフォルダーを整理する方法とは関係ありません。

于 2012-04-20T20:38:38.837 に答える
1

2つの別々のデータ構造を使用します。

  1. 検索用の二分探索木
  2. そして表現のための一般的な二分木

これら2つをリンクします。

ノート：

  • 一般に、ツリーはフォルダーを最初に配置し、すべてのファイルを最後の1つのノードとしてBSTに配置します。

または使用：

Node:
    Node* Left_Most_Child_Folder;
    Node* Right_Sibling_Folder;
    BST_Node* Files_Root;
于 2012-04-20T20:18:17.827 に答える
0

これを行う1つの方法は、二分木の二分木を使用することです。例えば：

Node
  Node* Children;
  Node* Left;
  Note* Right;

そして、あなたのツリーのルートはNode*です。

これにより、ノードのトラバースが容易になり、ノードの挿入と削除が迅速になります。もちろん、ノードを挿入するレベルへのパス、または削除するノードへのパスがわかっている場合に限ります。しかし、エクスプローラーに似たモデルが必要だと言っているので、特定のレベルを見つけても問題はないと思います。

特定のレベルでノードを検索するのは、二分木を検索するのと同じくらい簡単です。

モデル化しようとしているものについてもう少し情報がなければ、それが私にできる最善のことです。

于 2012-04-20T17:32:30.800 に答える