如何在不使用递归的情况下遍历二叉搜索树？

Question

我可以使用递归轻松遍历二叉搜索树，但我不知道如何在没有递归的情况下遍历二叉搜索树，所以请任何人解释一下，.....

Answer 1

是的，你可以用堆栈来做到这一点。你必须在这里采用 stack 算法，以二叉搜索树的迭代方式（非递归方式/方法）进行预重排序、中序和后序遍历。希望你能得到适当的帮助。

预购：

1）创建一个空栈node_Stack，并将根节点压入栈中。

2）当node_Stack不为空时执行以下操作。

-> 从堆栈中弹出一个项目并打印它。

-> 将弹出项目的右子元素推入堆栈

-> 将弹出项目的左子项推入堆栈

为了：

1）创建一个空栈S。

2) 将当前节点初始化为root

3）将当前节点压入S，并设置current = current->left，直到current为NULL

4) 如果 current 为 NULL 并且堆栈不为空则

 -> Pop the top item from stack.

 -> Print the popped item, set current = popped_item->right 

 -> Go to step 3.

5) 如果 current 为 NULL 并且 stack 为空，那么我们就完成了。

订单后：

1.1 创建空栈

2.1 当 root 不为 NULL 时执行以下操作

-> Push root's right child and then root to stack.

-> Set root as root's left child.

2.2 从堆栈中弹出一个项目并将其设置为根。

-> If the popped item has a right child and the right child 
   is at top of stack, then remove the right child from stack,
   push the root back and set root as root's right child.

-> Else print root's data and set root as NULL.

2.3 当堆栈不为空时，重复步骤2.1和2.2。