Forest of tree nodes C++?

Hey, I am trying to create a "forest" of tree nodes. A user will input two forests.. For example,

Forest1 :

a

_ _b

c

where b is a child tree/node of a.

Forest2:

d

e

_ _f

_ _ _ _g

_ _h

where d is a parent, e is the parent of f and h, f is the parent of g. f and h are siblings.

Anyway, I have two questions that I've been stuck on for awhile:

What is the best way to get this input (from a unix sys开发者_如何学Ctem?) line by line?

And, what is the best way to traverse this in order to get parents and children.

Any other tips are appreciated also, thanks!!

You could use Lisp like syntax for input:

(a (b)) (c)

(d) (e (f (g)) (h))

I used Boost.Graph library for similar purpose. It's a very good implementation but it require modest time to be familiar with.

It doesn't really matter too much on what kind of system you're on, but yes, process it line by line using an ifstream. There really isn't a "best way" to traverse this I don't think, as it is a text file and someone can pass you a txt file formatted in any weird way; so you should consider that and try to handle all cases as best as you can.

So, let's try stepping through how you can do this.

You're in a loop processing this line by line, your current node is set to NULL as a parent hasn't been processed yet. Read in the line and look for an underscore at the beginning of the string; if parent is null, well then wee have a line that can't be processed, so skip it. If the first character isn't an underscore, set this to the current parent node and move on to the next part of the loop. If there is an underscore and the current parent isn't null, then iterate through the remaining number of underscores and iterate down the children of nodes inside of the parent.

Actually, I just had a better idea, but this will give you something to think about at least. Cheers, let me know what you come up with.

You can process the input character by character (i think it's a little easier this way).

If your tree is not binary (that is, a node can have more than 2 children), it might be worthwhile to introduce a "virtual" parent node that has all the real roots as its child nodes. This will eliminate some annoying special cases (e.g. forest is empty), especially in traversal.

It might be good to add a pointer from child to parent; if you want to support iterators in your tree, this would be useful. However, if you don't need complicated things to do during traversal, you can implement it recursively, and then you don't need any child-to-parent pointers.