C++ STL 类 std::map 使用二叉树实现 O(log(n)) 查找。但是对于树，迭代器如何工作并不是很明显。++ 运算符在树结构中的实际含义是什么？尽管“下一个元素”的概念在数组中有明显的实现，但对我来说，在树中并不那么明显。如何实现树迭代器？
最佳答案
对于中序遍历(可能也适用于其他人)，如果您的节点中有父指针，则可以进行非递归遍历。应该可以只在迭代器中存储两个指针:您需要指示您在哪里，并且您可能(我现在不做研究)需要类似“previous”指针的东西，这样您就可以弄清楚你当前的移动方向(即我需要进入左子树，还是我刚从它回来)。
如果我们刚刚进入节点，“Previous”将可能类似于“父级”； “left”如果我们从左子树返回，“right”如果我们从右子树返回，“self”如果我们返回的最后一个节点是我们自己的。
关于c++ - std::map 迭代器如何工作？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12259571/