1

我一直在阅读有关树数据结构来建模问题的信息。我需要构建与文件系统中的文件夹/文件表示非常相似的数据的内存表示（我不是暗示存储在磁盘中的实际文件，而是像资源管理器一样的结构）。树可能最大 10 深 中间节点可能只有中等数量的子节点（比如 10 ），但可能有数千个叶节点。[就像文件夹中的数千个文件，文件是叶节点]

一些想法

  • 二叉树不能工作，因为一个节点最多只能有两个孩子。（假设我们可以有 3 个子文件夹）
  • 一个非常通用的树实现可能效率低下，因为我的数据可以排序。就像左边的兄弟姐妹比右边的兄弟姐妹更小/更小。我希望这可以进行有效的遍历。
  • B树听起来很接近，但它是否坚持平衡要求。就我而言，深度不会超过 10，但不一定所有分支都那么深。（比如 c:/windows ，C:/MyDoc../A/B/C）

请帮助您的经验。我是否应该自定义创建树或任何合适的数据结构（并不意味着特定于编程语言）

4

4 回答 4

3

您有两种不同类型的节点：文件和文件夹。

文件夹节点包含一组子节点（或映射），其中子节点本身可能是文件或文件夹。

或者，您可能希望文件夹节点包含一组文件和一组文件夹。

对于集合，只需使用您最喜欢的有序集合表示（可能是您使用的任何语言附带的表示）。根据您的具体情况，您可能更喜欢使用地图。

于 2012-04-20T19:01:06.513 回答
1

在典型的文件系统中，“目录树”和搜索树不是一回事，通常是分开维护的。“目录树”告诉你一个文件夹有哪些文件/子文件夹，或者一个特定文件的路径，它只是反映了用户如何组织文件并且只对用户有用。另一方面，搜索树维护了所有文件的全局索引，以便于快速搜索。

例如，您可以实现类似 Linux 的文件系统，其中文件夹是记录其包含的其他文件/文件夹的指针的文件。同时你维护一个 B+ 树，它把每个文件指针作为一个叶子。B+树的平衡状况与用户如何组织文件夹无关。

于 2012-04-20T20:38:38.837 回答
1

使用两个独立的数据结构：

  1. 用于搜索的二叉搜索树
  2. 以及用于表示的通用二叉树

并将这两者联系在一起。

笔记：

  • 一般来说，树将文件夹按顺序放在首位，然后将所有文件放在 BST 中作为最后一个节点。

或使用：

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

一种方法是使用二叉树的二叉树。例如：

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

你的树的根是Node*.

这使得节点的遍历和快速插入和删除变得容易。当然，前提是您知道要插入节点的级别的路径，或者要删除的节点的路径。但是由于您表示您想要一个类似于 Explorer 的模型，我假设找到特定级别不会造成问题。

在特定级别搜索节点就像搜索二叉树一样简单。

如果没有关于您要建模的内容的更多信息，那是我能做的最好的事情。

于 2012-04-20T17:32:30.800 回答