C++ STL中set和map的先序遍历和后序遍历

Question

我了解c++ STL中提供的集合和映射是基于树实现的，那么我是否可以将它们作为树来遍历？我是否可以得到集合或映射的前序遍历和后序遍历？我知道通过简单地迭代所有元素可以获得中序遍历。

set<int> tree;
tree.insert(1);
tree.insert(2);
tree.insert(3);

这棵树的中序遍历应该是1、2、3，前序遍历是2、1、3，后序遍历是1、3、2。如果我有一组树，如何得到第二个遍历结果呢？

谢谢！

- Naveen Mittal

---

“一棵树”，但不是任何具体的树。地图和集合允许您按键顺序对值进行有序迭代。树的细节未公开或可观察。 - Kerrek SB

@KerrekSB 说：“不可见或不可观察”，但实际上很多人都默认认为std::map是红黑树。https://dev59.com/HnVC5IYBdhLWcg3wtzkQ - Sergey Kolesnik

Answer 1

Stl set和map是平衡树（如红黑树）。它们不仅插入元素并将其保持在一个顺序中，还可以平衡它们的元素以保持树的O(logn)高度。因此，您的元素不一定在树中看起来像您想象的那样，并且没有函数可以让您查看它们的方式。

- misztsu