本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法。分享给大家供大家参考，具体如下：
1. 分析
二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。
深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。具体说明如下：先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。
2. 举例说明
对下图所示的二叉排序树进行遍历，要求使用先序遍历（递归、非递归）、中序遍历（递归、非递归）、后序遍历（递归、非递归）和广度优先遍历。
① 参考代码package BinaryTreeTraverseTest;import java.util.LinkedList;import java.util.Queue;/*** 二叉树的深度优先遍历和广度优先遍历* @author Fantasy* @version 1.0 2016/10/05 - 2016/10/07*/ public class BinaryTreeTraverseTest {public static void main(String[] args) {BinarySortTree tree = new BinarySortTree();tree.insertNode(35);tree.insertNode(20);tree.insertNode(15);tree.insertNode(16);tree.insertNode(29);tree.insertNode(28);tree.insertNode(30);tree.insertNode(40);tree.insertNode(50);tree.insertNode(45);tree.insertNode(55);System.out.print("先序遍历（递归）：");tree.preOrderTraverse(tree.getRoot());System.out.println();System.out.print("中序遍历（递归）：");tree.inOrderTraverse(tree.getRoot());System.out.println();System.out.print("后序遍历（递归）：");tree.postOrderTraverse(tree.getRoot());System.out.println();System.out.print("先序遍历（非递归）：");tree.preOrderTraverseNoRecursion(tree.getRoot());System.out.println();System.out.print("中序遍历（非递归）：");tree.inOrderTraverseNoRecursion(tree.getRoot());System.out.println();System.out.print("后序遍历（非递归）：");tree.postOrderTraverseNoRecursion(tree.getRoot());System.out.println();System.out.print("广度优先遍历：");tree.breadthFirstTraverse(tree.getRoot());}}/*** 结点*/ class Node> {E value;Node left;Node right;Node(E value) {this.value = value;left = null;right = null;}}/*** 使用一个先序序列构建一棵二叉排序树（又称二叉查找树）
*/ class BinarySortTree> {private Node root;BinarySortTree() {root = null;}public void insertNode(E value) {if (root == null) {root = new Node(value);return;}Node currentNode = root;while (true) {if (value.compareTo(currentNode.value) > 0) {if (currentNode.right == null) {currentNode.right = new Node(value);break;}currentNode = currentNode.right;} else {if (currentNode.left == null) {currentNode.left = new Node(value);break;}currentNode = currentNode.left;}}}public Node getRoot(){return root;}/*** 先序遍历二叉树（递归）
* @param node*/ public void preOrderTraverse(Node node) {System.out.print(node.value + " ");if (node.left != null) preOrderTraverse(node.left);if (node.right != null) preOrderTraverse(node.right);}/*** 中序遍历二叉树（递归）
* @param node*/ public void inOrderTraverse(Node node) {if (node.left != null) inOrderTraverse(node.left);System.out.print(node.value + " ");if (node.right != null) inOrderTraverse(node.right);}/*** 后序遍历二叉树（递归）
* @param node*/ public void postOrderTraverse(Node node) {if (node.left != null) postOrderTraverse(node.left);if (node.right != null) postOrderTraverse(node.right);System.out.print(node.value + " ");}/*** 先序遍历二叉树（非递归）
* @param root*/ public void preOrderTraverseNoRecursion(Node root) {LinkedList> stack = new LinkedList>();Node currentNode = null;stack.push(root);while (!stack.isEmpty()) {currentNode = stack.pop();System.out.print(currentNode.value + " ");if (currentNode.right != null) stack.push(currentNode.right);if (currentNode.left != null) stack.push(currentNode.left);}}/*** 中序遍历二叉树（非递归）
* @param root*/ public void inOrderTraverseNoRecursion(Node root) {LinkedList> stack = new LinkedList>();Node currentNode = root;while (currentNode != null || !stack.isEmpty()) {// 一直循环到二叉排序树最左端的叶子结点（currentNode是null）
while (currentNode != null) {stack.push(currentNode);currentNode = currentNode.left;}currentNode = stack.pop();System.out.print(currentNode.value + " ");currentNode = currentNode.right;}}/*** 后序遍历二叉树（非递归）
* @param root*/ public void postOrderTraverseNoRecursion(Node root) {LinkedList> stack = new LinkedList>();Node currentNode = root;Node rightNode = null;while (currentNode != null || !stack.isEmpty()) {// 一直循环到二叉排序树最左端的叶子结点（currentNode是null）
while (currentNode != null) {stack.push(currentNode);currentNode = currentNode.left;}currentNode = stack.pop();// 当前结点没有右结点或上一个结点（已经输出的结点）是当前结点的右结点，则输出当前结点while (currentNode.right == null || currentNode.right == rightNode) {System.out.print(currentNode.value + " ");rightNode = currentNode;if (stack.isEmpty()) {return; //root以输出，则遍历结束}currentNode = stack.pop();}stack.push(currentNode); //还有右结点没有遍历currentNode = currentNode.right;}}/*** 广度优先遍历二叉树，又称层次遍历二叉树* @param node*/ public void breadthFirstTraverse(Node root) {Queue> queue = new LinkedList>();Node currentNode = null;queue.offer(root);while (!queue.isEmpty()) {currentNode = queue.poll();System.out.print(currentNode.value + " ");if (currentNode.left != null) queue.offer(currentNode.left);if (currentNode.right != null) queue.offer(currentNode.right);}}}
② 输出结果先序遍历（递归）：35 20 15 16 29 28 30 40 50 45 55
中序遍历（递归）：15 16 20 28 29 30 35 40 45 50 55
后序遍历（递归）：16 15 28 30 29 20 45 55 50 40 35
先序遍历（非递归）：35 20 15 16 29 28 30 40 50 45 55
中序遍历（非递归）：15 16 20 28 29 30 35 40 45 50 55
后序遍历（非递归）：16 15 28 30 29 20 45 55 50 40 35
广度优先遍历：35 20 40 15 29 50 16 28 30 45 55更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》希望本文所述对大家java程序设计有所帮助。
您可能感兴趣的文章:简单谈谈Java遍历树深度优先和广度优先的操作方式Java分别利用深度优先和广度优先求解迷宫路径Java编程实现基于图的深度优先搜索和广度优先搜索完整代码深度优先与广度优先Java实现代码示例Java实现深度优先搜索(DFS)和广度优先搜索(BFS)算法
