前言

由于一直对广度优先遍历和深度优先遍历不是特别清楚，希望写下这篇文章加深自己的印象，并且能写出二叉树的广度优先遍历和深度优先遍历的代码。

广度优先遍历(层次遍历)

例如：

广度优先遍历的结果：A B C D E

其实可以把广度优先遍历理解成队列的形式，如图

对示例图的解释：首先根节点A进入队列，因为没有同级的节点，所以A出队，然后由A的子节点BC进入队列，B出队，B的子节点DE入队，C出队，C没有子节点，D出队，D没有子节点，E出队，E没有子节点。最后出队的顺序就是广度优先遍历的顺序 A B C D E

java代码实现

节点定义

public class TreeNode { String val; TreeNode left; TreeNode right; public String getVal() {return val;} public void setVal(String val) {this.val = val;} public TreeNode getLeft() {return left;} public void setLeft(TreeNode left) {this.left = left;} public TreeNode getRight() {return right;} public void setRight(TreeNode right) {this.right = right;} public TreeNode(String x) { val = x; } } //广度优先遍历 public static void BFS(TreeNode node){ if(node==null) return; //使用队列实现 发现java中又一堆队列，现在先选一个完成，后续再查阅相关资料 LinkedList queue = new LinkedList(); if (node != null) queue.add(node); while (!queue.isEmpty()){ node = (TreeNode) queue.poll(); System.out.println(node.getVal()); if (node.getLeft() != null) queue.add(node.getLeft()); if (node.getRight() != null) queue.add(node.getRight()); } }

深度优先遍历

例如：

深度的优先遍历的话有三种，先序遍历，中序遍历，后续遍历

先序：A B D E C

中序：D B E A C

后序：D E B C A

深度优先可以使用栈实现，也可以使用递归实现

1、java代码实现 递归实现

节点定义 同广度优先

//使用先序，注释掉中序和后序就可以了 如此类推 public static void depthRecursion(TreeNode node){ //先序 System.out.println(node.getVal()); if (node.getLeft() != null) depthRecursion(node.getLeft()); if (node.getRight() != null) depthRecursion(node.getRight()); //中序 if (node.getLeft() != null) depthRecursion(node.getLeft()); System.out.println(node.getVal()); if (node.getRight() != null) depthRecursion(node.getRight()); //后序 if (node.getLeft() != null) depthRecursion(node.getLeft()); if (node.getRight() != null) depthRecursion(node.getRight()); System.out.println(node.getVal()); }

2、java代码实现 栈实现 非递归

//使用先序，注释掉中序和后序就可以了 如此类推 public static void DFS(TreeNode node){ //先序 LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); stack.push(node); //push 在头部添加 while (!stack.isEmpty()){ node = stack.poll(); System.out.println(node.getVal()); if (node.getRight() != null) stack.push(node.getRight()); if (node.getLeft() != null) stack.push(node.getLeft()); } //中序 LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); stack.push(node); //push 在头部添加 while (!stack.isEmpty()){ //将左节点一直添加到队列中 while (node.getLeft() != null){ node = node.getLeft(); stack.push(node); } node = stack.pop(); System.out.println(node.getVal()); if (node.getRight() != null){ node = node.getRight(); stack.push(node); } } //后序 LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); TreeNode rightNode = null; while (node != null || !stack.isEmpty()){ //将左节点一直添加到队列中 while (node != null ||node!= null){ stack.push(node); node = node.getLeft(); } node = stack.pop(); //当前结点没有右节点或上一个输出的节点是当前节点的右节点，输出当前节点 while (node.getRight() == null || node.getRight() == rightNode){ System.out.println(node.getVal()); rightNode = node; if (stack.isEmpty()) return; node = stack.pop(); } stack.push(node); //右节点未遍历，还需要将节点加入 node = node.getRight(); } }

例子：利用BFS和DFS求二叉树的深度

BFS 使用队列

public static int depthBFS(TreeNode node){ LinkedList queue = new LinkedList(); if (node != null) { queue.add(node); } int depth = 1; while (!queue.isEmpty()){ int size = queue.size(); for (int i = 0; i < size; i++){ node = (TreeNode) queue.pop(); if (node.getLeft() == null && node.getRight() == null) return depth; if (node.getLeft() != null) queue.add(node.getLeft()); if (node.getRight() != null) queue.add(node.getRight()); } depth ++; } return depth; }

DFS 使用递归

public static int depthDFS(TreeNode node){ if (node == null) return 0; int left = depthDFS(node.getLeft()) + 1; int right = depthDFS(node.getRight()) + 1; return left > right ? left : right; }

如有错误希望指出，谢谢。