对于inorder遍历(可能也适用于其他人),如果节点中有父指针,则可以执行非递归遍历.应该可以在迭代器中存储两个指针:你需要指示你的位置,你可能(我现在不做研究)需要类似"前一个"指针的东西,这样你就可以搞清楚你当前的运动方向(即我需要进入左侧子树,还是我刚从它回来).
如果我们刚进入节点,"上一个" 可能会像 "父" 一样 ; 如果我们从左子树回来,"向左",如果我们从正确的子树回来,则"向右",如果我们返回的最后一个节点是我们自己的,则"自".
小智 5
我想添加我的两分钱\xc2\xa0worth作为评论，但由于我无法添加答案。\xc2\xa0我一直在谷歌搜索\xc2\xa0并感到沮丧，因为所有答案\ xc2\xa0我发现，这些除外，假设有一个堆栈或其他一些可变大小的数据结构。我确实找到了一些代码.\xc2\xa0 它表明它可以在没有 \xc2\xa0a 堆栈的情况下完成，但我发现很难遵循，因此决定从第一原理开始解决问题。
\n首先要注意的是，该算法是“左贪婪”的。\xc2\xa0 因此，当我们从根开始时，我们立即尽可能向左走，因为最左边的节点是我们首先需要的节点。\xc2 \xa0 这个\xc2\xa0意味着我们永远不需要考虑左子树。\xc2\xa0它已经被迭代了\xc2\xa0over。
\n迭代的顺序是左子树，节点，右子树。\xc2\xa0 因此，如果我们位于给定节点，我们知道它的左子树和节点本身已被访问，并且我们接下来应该访问右子树，如果任何，尽可能向左走。
\n否则，我们必须沿着树向上走。\xc2\xa0 如果我们从左子树到它的父树，那么接下来就是父树。\xc2\xa0（之后我们\xc2\xa0将访问\xc2\xa0它的右子树，如下所示）已经涵盖了。）
\n最后一种情况是当我们\xc2\xa0从右子节点到它的父节点时。\xc2\xa0 父节点已经被访问过，所以我们必须再次向上。\xc2\xa0 事实上我们必须继续向上直到我们到达根或树，或者发现我们从 \xc2\xa0 的左子节点移动到父节点。正如我们已经看到的，在这种情况下，父节点是下一个节点。\xc2\xa0（\xc2\xa0root 可能由空指针表示\xc2\xa0，如我的代码中那样，\xc2\xa0 或一些特殊的\xc2 \xa0sentinel 节点。）
\n下面的代码可以很容易地\xc2\xa0适用于STL风格的迭代器
\n// Go as far left from this node as you can.\n// i.e. find the minimum node in this subtree\nNode* Leftmost(Node* node)\n{\n if (node == nullptr)\n return nullptr;\n while (node->left != nullptr)\n node = node->left;\n return node;\n}\n\n// Start iterating from a root node\nNode* First(Node* root)\n{\n return Leftmost(root);\n}\n\n// The iteration is current at node. Return the next node\n// in value order.\nNode* Next(Node* node)\n{\n // Make sure that the caller hasn\'t failed to stop.\n assert(node != nullptr);\n\n // If we have a right subtree we must iterate over it,\n // starting at its leftmost (minimal) node.\n\n if (node->right != nullptr)\n return Leftmost(node->right);\n \n // Otherwise we must go up the tree\n\n Node* parent = node->parent;\n if (parent == nullptr)\n return nullptr;\n\n // A node comes immediately after its left subtree\n\n if (node == parent->left)\n return parent;\n\n // This must be the right subtree!\n assert(node == parent->right);\n\n // In which case we need to go up again, looking for a node that is\n // its parent\'s left child.\n\n while (parent != nullptr && node != parent->left)\n {\n node = parent;\n parent = node->parent;\n }\n\n // We should be at a left child!\n assert(parent == nullptr || node == parent->left);\n\n // And, as we know, a node comes immediately after its left subtree\n\n return parent;\n}\n