I was just thinking about implementing a binary tree with its root pointing to the parent folder and then the children pointing to subdirs nested within to store a directory structure in a binary tree.
I am not sure how to cater this problem with binary trees or if its possible?
M-way trees seems like the correct way of approaching this problem.
However, using linked list instead of a single node for binary trees and then dividing subdirs/2 at every level and storing them respectively in the left and right nodes(linked list), ensuring every node points to exactly two linked lists (left & right) which further store the subdirs.
Still confused on how to approach this
any suggestions?
Best Answer
Sufficient effort can make most things work, but I personally probably wouldn't use a plain binary tree for this in the future, and never have in the past. Here's an outline of the options as I see them:
It's worth noting that e.g. Unix-style directories can have multiple parents, as both symbolic links (text files, as I recall), and hard links (which are implemented by the actual filesystem itself) allow multiple directories to all include the same directory as one of their children (even if that child is one of those parent directories, as I recall); thus the simplest binary tree system couldn't properly represent Unix directories.
Similarly, you probably want to support more than two child directories.
I recommend against the simplest binary implementation.
I don't really suggest this because I consider it to mix different aspects of the subject too much, but it's worth considering.
Regardless, unless you're going for option (1), M-way trees are an optimization instead of a completely distinct method. I suggest them for later optimizations.
I recommend against simple implementations of tries.
If you want to use only a single format of node, then this is probably your best bet. I conditionally (you want a single node format) recommend in favor of "decorated" tries.
I strongly recommend internally complex tries. (2), (3), and hash-tables can be mixed in if optimization dictates, and in the meantime a fully-capable system can be created with a relatively minor amount of complication in comparison to a simple binary tree. If multiply-parented directories are desired, then the directories can each be separated into a distinct trie, with an additional system to indicate parent directories, whether a "reversal" flag as in (2), a "search stack" system that completely removes parentage tracking from the system, and instead tracks how a particular search got to the current directories, or even some mixture of techniques.
Personally, I've always gone with (6). I consider it's separation-of-concerns to be particularly desirable. If you have a particular requirement that forces you into something else, I would advise running option (6) by the specifier, just to see if they consider it compliant with the part of the requirement that you're concerned about.