大连h5建站,网页设计与制作教程赵祖荫下载,wordpress用户积分,网络服务器有哪些DFS(depth first search) 深度优先遍历
从图中一个未访问的顶点V开始#xff0c;沿着一条路一直走到底#xff0c;然后从这条路尽头的节点回退到上一个节点#xff0c;再从另一条路走到底…不断递归重复这个过程#xff0c;直到所有的顶点都遍历完成。前序遍历#xff0c…DFS(depth first search) 深度优先遍历
从图中一个未访问的顶点V开始沿着一条路一直走到底然后从这条路尽头的节点回退到上一个节点再从另一条路走到底…不断递归重复这个过程直到所有的顶点都遍历完成。前序遍历还是中序遍历亦或是后序遍历都属于深度优先遍历。
树是图的一种特例连通无环的图就是树接下来我们来看看树用深度优先遍历该怎么遍历。
1、我们从根节点 1 开始遍历它相邻的节点有 234先遍历节点 2再遍历 2 的子节点 5然后再遍历 5 的子节点 9。 2、上图中一条路已经走到底了9是叶子节点再无可遍历的节点此时就从 9 回退到上一个节点 5看下节点 5 是否还有除 9 以外的节点没有继续回退到 22 也没有除 5 以外的节点回退到 11 有除 2 以外的节点 3所以从节点 3 开始进行深度优先遍历如下 3、同理从 10 开始往上回溯到 6, 6 没有除 10 以外的子节点再往上回溯发现 3 有除 6 以外的子点 7所以此时会遍历 7
3、从 7 往上回溯到 3 1发现 1 还有节点 4 未遍历所以此时沿着 4 8 进行遍历,这样就遍历完成了
完整的节点的遍历顺序如下节点上的的蓝色数字代表
1.递归实现 public void dfs(TreeNode root){if (root null){return;}System.out.println(root.val);dfs(root.left);dfs(root.right);}存在的问题:如果层次太深容易造成栈溢出
2.非递归实现
1.使用栈实现对于每个节点先遍历当前节点然后吧右节点压栈再压左节点。 2.弹栈每弹出一个重复1 每弹出一个节点将这个节点的右节点和左节点放入栈直到栈为空。
public void dfsTest02(TreeNode treeNode){if (treeNode null){return;}StackTreeNode stack new Stack();stack.add(treeNode);while (!stack.isEmpty()){TreeNode peek stack.pop();System.out.println(peek.val);if (peek.right ! null){stack.add(peek.right);}if (peek.left ! null){stack.add(peek.left);}}
}BFS(breath first search) 广度优先遍历/层序遍历
使用队列来实现每次访问到的节点放入队列里面每次从队头取一个节点并将这节点的所有子节点存入队列直到队列为空。 public void bfs(TreeNode root){if (root null){return;}QueueTreeNode queue new LinkedList();queue.add(root);while (!queue.isEmpty()){TreeNode target queue.poll();System.out.println(target.val);if (target.left ! null){queue.add(target.left);}if (target.right ! null){queue.add(target.right);}}}
