二叉树的深度优先遍历与广度优先遍历
2014年11月22日
评论已被关闭
二叉树的深度优先遍历就是二叉树地前序遍历．二叉树的广度遍历就是层序遍历.（最后面有完整的代码）．
一．深度优先遍历(DFS)
深度优先遍历与前序遍历的结果是一样的．那么递归实现应该是
|
1 2 3 4 5 6 7 8 9 10 11 |
void dfs_r(T) { if (T == NULL) { return ; } print(T.k); dfs_r(T.left); dfs_r(T.right); } |
与之对应的非递归算法是，使用栈的先进后出的特性．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void dfs(T) { push(q,T); while (!is_empty(q)) { n = pop(q); print(n.k); if (n.right) { push(q,n.right); } if (n.left) { push(q,n.left); } } } |
二.广度优先遍历(BFS)
二叉树的广度优先遍历其实很简单，大概的思路是访问一个结点时，将它的子结点放入队列后面，当本层访问结束后，队列中就剩下下一层的所有结点，直到队列中没有结点为止．
可以看到队列的前部是当前层剩下的结点，队列的后部是当前层已经访问过的结点的子结点．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void bfs(T) { push(s,T); while (!is_empty(s)) { n = pop(s); print(n.k); if (n.left) { push(s,n.left); } if (n.right) { push(s,n.right); } } return ; } |
完整代码 阅读全文…
分类: 算法导论