java二叉树遍历

2024-04-29 19:39| 来源: 网络整理| 查看: 265

介绍

深度优先遍历：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。

广度优先遍历：从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。

DFS实现：

数据结构：栈

父节点入栈，父节点出栈，先右子节点入栈，后左子节点入栈。递归遍历全部节点即可

BFS实现：

数据结构：队列

父节点入队，父节点出队列，先左子节点入队，后右子节点入队。递归遍历全部节点即可

树的实现 public class TreeNode { private V value; private List childList;//子节点列表 public TreeNode(V value) { this.value = value; } public TreeNode(V value, List childList) { this.value = value; this.childList = childList; } public V getValue() { return value; } public void setValue(V value) { this.value = value; } public List getChildList() { return childList; } public void setChildList(List childList) { this.childList = childList; } } 深度优先搜索算法（DFS）

深度优先搜索算法是指沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

递归实现 public static void dfs(TreeNode tree, int depth) { if (tree != null) { //打印节点值以及深度 System.out.println(tree.getValue().toString() + ", " + depth); if (tree.getChildList() != null && !tree.getChildList().isEmpty()) { for (TreeNode item : tree.getChildList()) { dfs(item, depth + 1); } } } } 非递归实现 public static void dfsNotRecursive(TreeNode tree) { if (tree != null) { //次数之所以用 Map 只是为了保存节点的深度， //如果没有这个需求可以改为 Stack Stack stack = new Stack(); Map root = new HashMap(); root.put(tree, 0); stack.push(root); while (!stack.isEmpty()) { Map item = stack.pop(); TreeNode 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 treeNode : node.getChildList()) { Map map = new HashMap(); map.put(treeNode, depth + 1); stack.push(map); } } } } } 分类

一般来说 DFS 算法又分为如下三种：

1.前序遍历(Pre-Order Traversal) ：指先访问根，然后访问子树的遍历方式

private static void dfs(TreeNode tree, int depth) { if (d != null) { //打印节点值以及深度 System.out.println(tree.getValue().toString() + ", " + depth); if (tree.getChildList() != null && !tree.getChildList().isEmpty()) { for (TreeNode item : tree.getChildList()) { dfs(item, depth + 1); } } } }

2.后序遍历(Post-Order Traversal)：指先访问子树，然后访问根的遍历方式

private static void dfs(TreeNode tree, int depth) { if (d != null) { if (tree.getChildList() != null && !tree.getChildList().isEmpty()) { for (TreeNode item : tree.getChildList()) { dfs(item, depth + 1); } } //打印节点值以及深度 System.out.println(tree.getValue().toString() + ", " + depth); } }

3.中序遍历(In-Order Traversal)：指先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式。中序遍历一般是用二叉树实现：

private static void dfs(TreeNode 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 void bfs(List children, int depth) { List thisChildren, allChildren = new ArrayList(); for (TreeNode 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 void bfsNotRecursive(TreeNode tree) { if (tree != null) { //跟上面一样，使用 Map 也只是为了保存树的深度，没这个需要可以不用 Map Queue queue = new ArrayDeque(); Map root = new HashMap(); root.put(tree, 0); queue.offer(root); while (!queue.isEmpty()) { Map itemMap = queue.poll(); TreeNode 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 child : itemTreeNode.getChildList()) { Map map = new HashMap(); map.put(child, depth + 1); queue.offer(map); } } } } }

【本文地址】

公司简介

联系我们