Java实现二叉树的深度优先遍历和广度优先遍历算法示例更新时间是在两千零一十八年四月十九号中午十二点零二分三十一秒, 由这位作者所发布的。这篇文章的重点, 是把用Java语言来实现二叉树深度优先遍历和广度优先遍历这样的算法, 给大伙儿说清楚。它会拿着具体例子, 一步一步地把二叉树是什么、怎么进行深度优先遍历、又该怎么搞广度优先遍历这些原理, 还有相关的操作技巧, 全都给你掰扯明白, 需要的人拿去看看。这篇文章的具体样例说明了, 如何使用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是nullwhile (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是nullwhile (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程序设计这个事情的阶段当中, 带来一些实际的、有用的帮助。