Path tree to tree structure

Question

Hello suppose you have ordinary unix path tree as input (as string).

root 0
root/file1.txt 1
root/file2.txt 2
root/folder1 3
root/folder1/file3.txt 4
root/folder1/file4.txt 5
e.t.c.

What is the better way to convert this string to tree data structure?

Q: What do you mean? Also: look here: http://stackoverflow.com/questions/205945/why-does-the-c-stl-not-provide-any-tree-containers — paulsm4, Aug 10 '12 at 22:28
I have path tree as string. I need to make tree data structure (c++ class) and reflect appropriate hierachy. — Alex Hoppus, Aug 10 '12 at 22:33
I don't think there is any best way. You just have to define your tree structure and parse your file. It's normal programming work in other words, no tricks. — jahhaj, Aug 10 '12 at 22:37
There is no "better" way. If you want a filesystem like tree, you need something like a dummy filesystem. Or you can just write a function that adds a full path at once. You should probably use std::map, first. — Evan Dark, Aug 10 '12 at 23:50

score 1 · Answer 1 · answered Aug 10 '12 at 23:21

1

something like this:

create a root node for '\'

node=root;
token=getNextToken(inputString);
while (token){
 if (!node.childExist(token)) node.createChild(token)
 node=node.Child(token)
 token=getNextToken(inputString);
}

answered Aug 10 '12 at 23:21

Gir

839
5
11

Yup - that's definitely a good algorithm for parsing the strings to build the tree. The next question is "What do I use to implement the tree?" That's where the link I cited above comes in: http://stackoverflow.com/questions/205945/why-does-the-c-stl-not-provide-any-tree-containers. As jahhaj said, there is no one, out of the box, built-in "Best Way". – paulsm4 Aug 10 '12 at 23:35
Gir: do not allowed to use any third - party libraries. What is node in your code? I – Alex Hoppus Aug 11 '12 at 09:12
paulsm4: i saw this link but i can't use boost graph library to solve this problem – Alex Hoppus Aug 11 '12 at 09:14
You dont need any third party libraries - you can write a tree class yourself – Gir Aug 11 '12 at 11:16

score 1 · Accepted Answer · answered Aug 11 '12 at 09:07

Now i use simple tree representation, created by myself

template<typename T>
class TreeNode
{
public:
    TreeNode() {};

    TreeNode(T)
    {
        value = T;
    }

    TreeNode(const T& value)
        : Value(value)
    {
    }

    T Value;
    vector<TreeNode<T>*> Children;
};

I don't really understand Gir's algorithm (posted above). But i suppose the solution must be the following:

1. Get a root node, set depth_level = 0
3. set support_node = root_node
4. for each path line
5.     determine the quantity of slashes "/", key and file(folder) name

so for example in string root/folder1/file4.txt 5, num of slashes = 2 filename = file4.txt, key = 5
       create current_node
6.     if num_of_slashes == level + 2
7.          set support_node = current_node
8.     if num_of_slashes == level + 1
9.          add children to support_node
10.    And after that we must remember all ancestors,  going down to leaves. Cuz we can  return to any ancestor.

For me this algorithm seems to be really complicated. I don't understand algorithm, posted above, maybe it is possible to clarify this question? Maybe the structure i use to store the tree isn't the best one?

Path tree to tree structure

2 Answers2