適合的樹型數據結構

我一直在閱讀關於樹型數據結構來模擬問題。我需要構建一個與文件系統中的文件夾/文件表示非常相似的數據的內存表示（我並不意味着存儲在磁盤中的實際文件，而是像結構的瀏覽器）。樹可能最大10深中間節點可能只有中等數量的子節點（比如說10），但可能有成千上萬個葉子節點[就像文件夾和文件中的數千個文件是葉節點]適合的樹型數據結構

的幾點思考

二叉樹不能工作作爲一個節點可以最多隻有2個孩子。（假設我們可以有3個子文件夾）
非常普遍的樹實現可能效率低下，因爲我的數據可以被排序。就像左邊的兄弟姐妹比右邊的兄弟姐妹小或小一樣。我希望這允許有效的遍歷。
B樹聽起來非常接近，但它堅持平衡要求。在我的情況下，深度不會超過10，但不一定是所有深的分支（如c：/ windows，C：/ MyDoc ../ A/B/C）

請幫助你的經驗。我應該自定義一棵樹還是可用的任何合適的數據結構（並不意味着特定於編程語言）

來源

2012-04-20 bsr

那麼......不要在B-Trees中實現平衡！ – ElKamina 2012-04-20 17:16:15

您有兩種不同的節點：文件和文件夾。

文件夾節點包含一組（或地圖）的子項，其中的子項本身可能是文件或文件夾。

或者，您可能希望文件夾節點包含一組文件和一組文件夾。

對於這些集合，只需使用您最喜歡的有序集合表示（可能是您使用的任何語言附帶的集合）。根據您的具體情況，您可能更願意使用地圖。

來源

2012-04-20 19:01:06

+1。這也被稱爲簡單的n元樹（每個內部節點有n個子元素，而二元樹則爲2個元素） - 特別是在子元素放入鏈表或數組類型的數據結構中。 – 2012-04-21 02:23:38

一種方法是使用二叉樹的二叉樹。例如：

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

而你的樹的根是Node*。

這使得易於遍歷和快速插入和刪除節點。當然，您可以知道要插入節點的級別的路徑，或者要刪除的節點的路徑。但是既然你表明你想要一個類似於資源管理器的模型，我認爲找到一個特定的級別不會造成問題。

在特定級別搜索節點與搜索二叉樹一樣簡單。

沒有關於你想要建模什麼的更多信息，這是我能做的最好的。

來源

2012-04-20 17:32:30

使用兩個單獨的數據結構：

二叉搜索樹搜索
而對於表示

一般二叉樹和鏈接在一起這兩個。

注：

一般樹的文件夾放在第一順序，並把所有的文件在BST作爲最後一個節點。

或使用：

Node: 
    Node* Left_Most_Child_Folder; 
    Node* Right_Sibling_Folder; 
    BST_Node* Files_Root;

來源

2012-04-20 20:18:17

在典型的文件系統中，「目錄樹」，並搜索樹是不一樣的東西，通常是單獨進行維護。「目錄樹」告訴你文件夾具有哪些文件/子文件夾或特定文件的路徑，只是反映了用戶如何組織文件並且僅對用戶有用。另一方面，搜索樹保持所有文件的全局索引，以便於快速搜索。

例如，您可以實現一個類似Linux的文件系統，其中文件夾是一個記錄其中包含的其他文件/文件夾的指針的文件。同時你維護一個B +樹，它將每個文件指針作爲一個葉子。 B +樹的平衡條件與用戶如何組織文件夾無關。

來源

2012-04-20 20:38:38 HelloWorld

適合的樹型數據結構

回答

相關問題