首页 > 算法导论 > 二叉树的深度优先遍历与广度优先遍历

二叉树的深度优先遍历与广度优先遍历

2014年11月22日

二叉树的深度优先遍历就是二叉树地前序遍历.二叉树的广度遍历就是层序遍历.(最后面有完整的代码).
一.深度优先遍历(DFS)

深度优先遍历与前序遍历的结果是一样的.那么递归实现应该是

与之对应的非递归算法是,使用栈的先进后出的特性.

二.广度优先遍历(BFS)

二叉树的广度优先遍历其实很简单,大概的思路是访问一个结点时,将它的子结点放入队列后面,当本层访问结束后,队列中就剩下下一层的所有结点,直到队列中没有结点为止.
可以看到队列的前部是当前层剩下的结点,队列的后部是当前层已经访问过的结点的子结点.

完整代码

分类: 算法导论 标签:
本文的评论功能被关闭了.