java二叉树遍历——深度优先(DFS)与广度优先(BFS) 递归版与非递
介绍深度优先遍历:从根节点出发,沿着左子树方向进行纵向遍历,直到找到叶子节点为止。然后回溯到前一个节点,进行右子树节点的遍历,直到遍历完所有可达节点为止。 广度优先遍历:从根节点出发,在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。 DFS实现: 数据结构:栈 父节点入栈,父节点出栈,先右子节点入栈,后左子节点入栈。递归遍历全部节点即可 BFS实现: 数据结构:队列 父节点入队,父节点出队列,先左子节点入队,后右子节点入队。递归遍历全部节点即可 树的实现public class TreeNode<V> { private V value; private List<TreeNode<V>> childList;//子节点列表 public TreeNode(V value) { this.value = value; } public TreeNode(V value,List<TreeNode<V>> childList) { this.value = value; this.childList = childList; } public V getValue() { return value; } public void setValue(V value) { this.value = value; } public List<TreeNode<V>> getChildList() { return childList; } public void setChildList(List<TreeNode<V>> childList) { this.childList = childList; } } 深度优先搜索算法(DFS)深度优先搜索算法是指沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。 递归实现public static <V> void dfs(TreeNode<V> tree,int depth) { if (tree != null) { //打印节点值以及深度 System.out.println(tree.getValue().toString() + "," + depth); if (tree.getChildList() != null && !tree.getChildList().isEmpty()) { for (TreeNode<V> item : tree.getChildList()) { dfs(item,depth + 1); } } } } 非递归实现public static <V> void dfsNotRecursive(TreeNode<V> tree) { if (tree != null) { //次数之所以用 Map 只是为了保存节点的深度, //如果没有这个需求可以改为 Stack<TreeNode<V>> Stack<Map<TreeNode<V>,Integer>> stack = new Stack<>(); Map<TreeNode<V>,Integer> root = new HashMap<>(); root.put(tree,0); stack.push(root); while (!stack.isEmpty()) { Map<TreeNode<V>,Integer> item = stack.pop(); TreeNode<V> node = item.keySet().iterator().next(); int depth = item.get(node); //打印节点值以及深度 System.out.println(tree.getValue().toString() + "," + depth); if (node.getChildList() != null && !node.getChildList().isEmpty()) { for (TreeNode<V> treeNode : node.getChildList()) { Map<TreeNode<V>,Integer> map = new HashMap<>(); map.put(treeNode,depth + 1); stack.push(map); } } } } } 分类一般来说 DFS 算法又分为如下三种: 1.前序遍历(Pre-Order Traversal) :指先访问根,然后访问子树的遍历方式 private static <V> void dfs(TreeNode<V> tree,int depth) { if (d != null) { //打印节点值以及深度 System.out.println(tree.getValue().toString() + ",depth + 1); } } } } 2.后序遍历(Post-Order Traversal):指先访问子树,然后访问根的遍历方式 private static <V> void dfs(TreeNode<V> tree,int depth) { if (d != null) { if (tree.getChildList() != null && !tree.getChildList().isEmpty()) { for (TreeNode<V> item : tree.getChildList()) { dfs(item,depth + 1); } } //打印节点值以及深度 System.out.println(tree.getValue().toString() + "," + depth); } } 3.中序遍历(In-Order Traversal):指先访问左(右)子树,然后访问根,最后访问右(左)子树的遍历方式。 private static <V> void dfs(TreeNode<V> root,int depth) { if (root.getLeft() != null){ dfs(root.getLeft(),depth + 1); } if (root.getRight() != null){ dfs(root.getRight(),depth + 1); } //打印节点值以及深度 System.out.println(d.getValue().toString() + "," + depth); } 广度优先搜索算法(Breadth-First Search,BFS)广度优先搜索算法是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。 递归实现public static <V> void bfs(List<TreeNode<V>> children,int depth) { List<TreeNode<V>> thisChildren,allChildren = new ArrayList<>(); for (TreeNode<V> child: children) { //打印节点值以及深度 System.out.println(child.getValue().toString() + "," + depth); thisChildren = child.getChildList(); if (thisChildren != null && thisChildren.size() > 0) { allChildren.addAll(thisChildren); } } if (allChildren.size() > 0) { bfs(allChildren,depth + 1); } } 递归实现的方式我自己想了好久没想出来,最后还是在网上搜到的算法。 非递归实现public static <V> void bfsNotRecursive(TreeNode<V> tree) { if (tree != null) { //跟上面一样,使用 Map 也只是为了保存树的深度,没这个需要可以不用 Map Queue<Map<TreeNode<V>,Integer>> queue = new ArrayDeque<>(); Map<TreeNode<V>,0); queue.offer(root); while (!queue.isEmpty()) { Map<TreeNode<V>,Integer> itemMap = queue.poll(); TreeNode<V> itemTreeNode = itemMap.keySet().iterator().next(); int depth = itemMap.get(itemTreeNode); //打印节点值以及深度 System.out.println(itemTreeNode.getValue().toString() + "," + depth); if (itemTreeNode.getChildList() != null && !itemTreeNode.getChildList().isEmpty()) { for (TreeNode<V> child : itemTreeNode.getChildList()) { Map<TreeNode<V>,Integer> map = new HashMap<>(); map.put(child,depth + 1); queue.offer(map); } } } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |