STL Map中的后序遍历

Question

我正在使用gcc编译器上的stl map，它使用树来存储键值对。迭代器按中序遍历方式前进，因此中序遍历非常容易。然而，我的一个输出要求是后序遍历。我被特别要求使用map。有没有办法实现后序遍历呢？

- Abhijeet Verma

---

从结尾开始向后移动？ - Kiril Kirov

我不确定对一个map进行后序遍历是否有意义，因为我怀疑在插入顺序不同的情况下，你可以得到略微不同形状的树，即使是相同的数据集。虽然所有这些可能的树的中序遍历将是相同的，但后序遍历将是不同的。 - Sergey Kalinichenko

Answer 1

没有标准的方法可以访问std::map实例的“实际树结构”。

此外，标准不知道（或者不关心）map元素在任何内部树中的排列方式。红黑树和AVL树都是std::map的有效实现，根据实际使用的树结构不同，您将获得不同的后序遍历结果。实际上，我预计它始终是R-B或非常相似的，但实现自由性影响了标准定义的接口。

简而言之，std::map不是一棵树，而是一个抽象数据结构，可以使用树来实现。

也许可以通过破解特定的实现来获取树结构，但最好不要这样做。如果您希望数据的树结构成为程序定义状态的一部分，则可以编写自己的树。

- Steve Jessop

Answer 2

正如Steve Jessop所说，Map是由C++提供的抽象数据结构，您无法更改存储在Map中元素的顺序，就像我们可以通过遍历预/后/中序来在树或AVL中进行操作一样。 但是，您可以通过使用std::greater作为键而不是std::less来反转存储顺序。

例如：

std::map< std::string, int, std::greater<std::string> > my_map; 

创建一个名为desiredOrder的向量，用于跟踪在映射中插入的顺序。一旦完成插入操作，只需对desiredOrder向量执行所需的排序操作（前置、后置或按顺序），然后使用for循环遍历向量，并使用向量值作为Map的键来访问Map元素。

e.g

std::vector<std::string> desiredOrder;
std::map<std::string, int> myTree;

myTree["A"] = 0;
desiredOrder.push_back("A"); 
myTree["B"] = 0;
desiredOrder.push_back("B");
myTree["C"] = 0;
desiredOrder.push_back("C");
myTree["D"] = 0;
desiredOrder.push_back("D");

/*
Do whatever sorting you want to do here....
*/

for (int i = 0; i < desiredOrder.size(); ++i)
{
    const std::string &s = desiredOrder[i];
    std::cout << s << ' ' << myTree[s] << '\n';
}

- Mahesh Mahindrakar

---

假设我们假定一个标准的平衡二叉树，反转顺序并不等同于使用后序遍历而不是中序遍历。 - jogojapan

谢谢...我不得不解释所有这些来消除后序需求... - Abhijeet Verma