适合的树型数据结构

我一直在阅读关于树型数据结构来模拟问题。我需要构建一个与文件系统中的文件夹/文件表示非常相似的数据的内存表示（我并不意味着存储在磁盘中的实际文件，而是像结构的浏览器）。树可能最大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

适合的树型数据结构

回答

相关问题