C++ STL 类 std::map 使用二叉树实现 O(log(n)) 查找。但对于树来说，迭代器如何工作并不是立即显而易见的。 ++ 运算符在树结构中实际上意味着什么？虽然“下一个元素”的概念在数组中有明显的实现，但对我来说，它在树中并不那么明显。如何实现树迭代器？
对于中序遍历（可能也适用于其他遍历），如果节点中有父指针，则可以进行非递归遍历。应该可以在迭代器中存储两个指针：您需要指示您所在的位置，并且您可能（我现在不做研究）需要类似“前一个”指针的东西，以便您可以弄清楚您当前的移动方向（即我是否需要进入左子树，或者我刚刚从左子树返回）。
“上一个”将probably be 就像是“parent”，如果我们刚刚进入节点；如果我们从左子树返回，则为“left”；如果从右子树返回，则为“right”；如果我们返回的最后一个节点是我们自己的节点，则为“self”。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
