二叉树的BFS与DFS遍历

二叉树的DFS遍历结果即前序遍历结果,BFS即层序遍历结果。
DFS用stack实现,或递归实现,BFS用队列实现。

中序访问的非递归写法和前序一样,都要用到一个栈来辅助存储,不一样的地方在于前序访问时,栈中保存的元素是右子树还没有被访问到的节点的地址,而中序访问时栈中保存的元素是节点自身和它的右子树都没有被访问到的节点地址。
后序遍历的非递归同样要借助一个栈来保存元素,栈中保存的元素是它的右子树和自身都没有被遍历到的节点,与中序遍历不同的是先访问右子树,在回来的时候再输出根节点的值。需要多一个last指针指向上一次访问到的节点,用来确认是从根节点的左子树返回的还是从右子树返回的。

图的BFS与DFS需要维护一个HashSet来存放访问过的节点,防止重复遍历

各种遍历方式参考链接
BFS&DFS参考链接

原文地址:https://www.cnblogs.com/WindyZ/p/13493733.html