如何有效地遍历多种类型的树？
我们都知道我们应该使用列表、双端队列或其他对象，而不是使用经典的链接列表，但是我的想法是类似链接列表的。
我有一个类型，我称之为 ABC。我可以通过 ABC root 访问所有内容。 ABC 类型可以容纳 0 个或多个 ABC。它还可以容纳 DE、FGH、D、E、F、G、H 类型。DE 还可以容纳 D 和 E 类型。FGH 可以容纳 FG、F、G、H。FG 可以容纳...您明白了。这些对象还可以保存 0 个或多个该类型及其子类型。
我面临的问题是如何以一种方式编写此代码，如果我处于类型 F，我可以调用parent() 并走回根类型 ABC？让我们暂时忘记类型并假设一切都是 BASE 类型。我如何用 C++ 编写这棵树？我正在考虑做这样的事情
class Base{
deque<Base*> children
Base*parent;
}
但这感觉就像一个链接列表。主要是因为沿着树向上走只是查看一个又一个的指针，这正是链接列表的作用，而沿着树向下走就是一个又一个指针双端队列的指针。有没有一些有效的方法来握住树木并行走？我的应用程序受 CPU 和内存限制，因此我不确定要进行哪种权衡。我如何保存这些数据？
We all know we should use a list, deque or another object instead of using the classic link-list however the way i am thinking is link-list like.
I have a type which i'll call ABC. I have access to everything through ABC root. The type ABC can hold 0 or many ABCs within. It can also hold type DE, FGH, D, E, F, G, H. DE can also hold type D and E. FGH can hold FG, F, G, H. FG holds... you get the idea. Those objects can also hold 0 or many of that type and its subtypes.
The problem i am facing is how do write this in a way that if i am in type F i can call parent() and walk my way back to the root type ABC? Lets actually forget about the types FOR NOW and assume everything is the type BASE. How would i write this tree in C++? I was thinking of doing something like this
class Base{
deque<Base*> children
Base*parent;
}
But this felt like a link list. Mostly because walking up the tree is just looking at pointer after pointer which is exactly what a link list does and walking down a tree is pointer after deque of pointers. Is there some efficient way of holding trees and walking it? My app is CPU and memory bound so i am not sure which tradeoff i want to make. How do i hold this data?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
呃，什么？
链表的 evar 用途并不多，但是当您需要类似 DAG 之类的东西时，几乎没有其他方法可以做到这一点。
只需使用指针即可。
Uh, wot?
Linked lists don't have the most uses evar, but when you need something like what you have, which is a DAG, then there's pretty much no other way to do it.
Just use the pointers.