树节点森林 C++?
嘿，我正在尝试创建一个树节点的“森林”。用户将输入两个森林.. 例如，
森林1：
一个
_ _b
c
其中 b 是 a 的子树/节点。
森林2：
d
电子
_ _f
_ _ _ _g
__h
其中 d 是父级，e 是 f 和 h 的父级，f 是 g 的父级。 f 和 h 是兄弟姐妹。
无论如何，我有两个问题已经困扰了一段时间：
逐行获取此输入（来自 UNIX 系统？）的最佳方法是什么？
并且，为了找到父母和孩子，穿越这个的最佳方式是什么？
任何其他提示也表示赞赏，谢谢！
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 system?) 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!!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可以使用类似 Lisp 的语法进行输入：
(a (b)) (c)
(d) (e (f (g)) (h))
我使用 Boost.Graph 库用于类似目的。这是一个非常好的实现，但需要一定的时间来熟悉。
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.
对于您使用的系统类型来说，这并不重要，但是，可以使用 ifstream 逐行处理它。我认为确实没有“最好的方法”来遍历这个文件，因为它是一个文本文件，有人可以向您传递一个以任何奇怪的方式格式化的 txt 文件；所以你应该考虑这一点，并尽可能地处理所有情况。
那么，让我们尝试逐步了解如何执行此操作。
您正在循环中逐行处理此节点，当前节点设置为 NULL，因为父节点尚未处理。读入该行并在字符串开头查找下划线；如果parent为空，那么我们有一行无法处理，所以跳过它。如果第一个字符不是下划线，则将其设置为当前父节点并继续循环的下一部分。如果存在下划线并且当前父节点不为空，则迭代剩余数量的下划线并向下迭代父节点内部节点的子节点。
事实上，我只是有一个更好的主意，但这至少会给你一些思考的机会。干杯，让我知道你的想法。
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.