“给出一个执行中序树遍历的非递归算法”。
这不就是标准的深度优先搜索吗？我在网上看到的针对此问题的非递归解决方案都没有做任何真正类似于 DFS 的事情(即使它们都使用堆栈)……我的推理不正确吗？
这是我的伪代码:
public inOrder(节点根):
创建新的 Stack -> s
创建新的 bool 集 -> 已访问
s.push(root)
同时(!s.isEmpty()):
当前节点 = s.pop()
打印(当前节点)
如果(!visited.contains(currNode)):
visited.add(当前节点)
如果(currNode.right != null):
s.push(currNode.right)
如果(currNode.left!= null):
s.push(currNode.left)
最佳答案
DFS 不一定是有序的，尽管有序就是 DFS。查看wikipedia article .任何递归函数都可以用堆栈非递归地实现(因为递归使用堆栈)。
通过将您的代码与维基百科文章中的前序、中序和后序遍历进行比较，您可以看到，您的代码遍历是预序的，因为它在子节点之前打印父节点。为了使这个实现成为中序遍历，必须先打印左节点。这可以通过
- 检查
currNode.left是否不为空且未被访问 - 如果 (1) 为真，推送
currNode和currNode.left - 如果(1)为假，将
currNode添加到访问集，打印currNode，如果存在currNode.right则推送。
关于algorithm - 如何打印 BST 的中序遍历？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38362311/