快捷搜索:  汽车  科技

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

二叉树的广度优先遍历代码(常见二叉树面试题)/** * 后根序遍历 * @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)相关知识。

二叉树的广度优先遍历代码(常见二叉树面试题)(1)

二叉树

深度优先遍历,指的是遍历一颗二叉树时,先尽可能的走到最深一层的节点,然后再考虑广度。如上图,先根序()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); // 在遍历右子树之后进行输出。 }

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

猜您喜欢: