二叉树的广度优先遍历代码（常见二叉树面试题）

二叉树的广度优先遍历代码（常见二叉树面试题）/** * 后根序遍历 * @param root */ public static void dfs(Node root) { if (root.left != null) { dfs(root.left); } if (root.right != null) { dfs(root.right); } System.out.println(root.value); // 在遍历右子树之后进行输出。 }最后，欢迎大家关注、转发。/** * 中根序遍历 * @param root */ public static void dfs(Node root) { if (root.left != null) { dfs(root.left); } System.out.println(root.value); // 在遍历左子树之后进行输出。 if (root.

面试中，谈到二叉树大家是不是容易紧张，各种红黑树、平衡树、大小堆，不要紧张。今天就开始逐个破解，首先来讲二叉树的深度优先遍历（DFS：Depth First Search）相关知识。

二叉树

深度优先遍历，指的是遍历一颗二叉树时，先尽可能的走到最深一层的节点，然后再考虑广度。如上图，先根序（）DFS）遍历的顺序应为：

A-B-D-E-C-F-G

这种深度优先搜索的代码实现其实非常简单，一般借助递归的思想，将当前节点值输出，然后递归左子树，再递归右子树。

废话不多说，看代码：

// 声明数据结构 class Node{ Node left; Node right; String value; public Node(String value) { this.value = value; } } public class DFS { public static void main(String[] args) { Node a = new Node("A"); Node b = new Node("B"); Node c = new Node("C"); Node d = new Node("D"); Node e = new Node("E"); Node f = new Node("F"); Node g = new Node("G"); a.left=b; a.right=c; b.left = d; b.right = e; c.left = f; c.right = g; dfs(a); } public static void dfs(Node root) { System.out.println(root.value); // 输出相应内容，或做些其他操作。 if (root.left != null) { dfs(root.left); } if (root.right != null) { dfs(root.right); } } } /* 输出为： D E B F G C A */

而中根序只需将输出代码移动到遍历左子树之后，此时输出顺序应为：“D-B-E-A-F-C-G”

/** * 中根序遍历 * @param root */ public static void dfs(Node root) { if (root.left != null) { dfs(root.left); } System.out.println(root.value); // 在遍历左子树之后进行输出。 if (root.right != null) { dfs(root.right); } }

后根序，则将输出代码放置到遍历右子树后即可，此时输出顺序为：“D-E-B-F-G-C-A”

/** * 后根序遍历 * @param root */ public static void dfs(Node root) { if (root.left != null) { dfs(root.left); } if (root.right != null) { dfs(root.right); } System.out.println(root.value); // 在遍历右子树之后进行输出。 }

最后，欢迎大家关注、转发。