概念定义：
深度优先遍历：深度优先遍历是图论中的经典算法。其利用了深度优先搜索算法可以产生目标图的相应拓扑排序表，采用拓扑排序表可以解决很多相关的图论问题，如最大路径问题等等。
根据深度优先遍历的特点我们利用Java集合类的栈Stack先进后出的特点来实现。我用二叉树来进行深度优先搜索。
广度优先遍历：广度优先遍历是连通图的一种遍历策略，因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域故得名。
根据广度优先遍历的特点我们利用Java数据结构队列Queue来实现。
代码：
public class TreeNode {
int data;
TreeNode leftNode;
TreeNode rightNode;
public TreeNode() {
}
public TreeNode(int d) {
data=d;
}
public TreeNode(TreeNode left,TreeNode right,int d) {
leftNode=left;
rightNode=right;
data=d;
}
}
package theTransverseOfDigram;
import java.lang.invoke.StringConcatException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Traverse {
public static void main(String[] args) {
TreeNode head = new TreeNode(1);
TreeNode second = new TreeNode(2);
TreeNode three = new TreeNode(3);
TreeNode four = new TreeNode(4);
TreeNode five = new TreeNode(5);
TreeNode six = new TreeNode(6);
TreeNode seven = new TreeNode(7);
head.right = three;
head.left = second;
second.right = five;
second.left = four;
three.right = seven;
three.left = six;
System.out.println("深度优先遍历的结果----");
new Traverse().deepTranverse(head);
System.out.println("广度优先遍历的结果---");
new Traverse().broadTranverse(head);
}
- 深度优先遍历代码
public void deepTranverse(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.println(node.data);
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
}
- 广度优先遍历代码
public void broadTranverse(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.println(node.data);
if (node.right != null) {
queue.add(node.right);
}
if (node.left != null) {
queue.add(node.left);
}
}
}
}