一、遍历算法介绍
遍历是指按照一定的顺序，对数据结构中的每个元素均访问一次而进行的操作。Java中常用的数据结构有数组、链表、集合和树等，不同的数据结构需要采用不同的遍历算法。
常见的遍历算法有以下几种：
1、线性结构遍历
线性结构遍历是指对于一维数组或链表这样的线性数据结构，按照顺序对每一个元素进行访问。具体实现可使用for循环或迭代器进行。
int[] arr = {1, 2, 3, 4};
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
List<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("cherry");
Iterator<String> it = list.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
2、树结构遍历
树结构遍历是指对于二叉树、多叉树等这样的树状数据结构，按照一定的顺序对每个节点进行访问。常见的树结构遍历算法有前序遍历、中序遍历和后序遍历。
前序遍历：按照根节点–>左子树–>右子树的顺序进行遍历。
class TreeNode{
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val = val;
}
}
public void preOrder(TreeNode root){
if(root == null)
return;
System.out.println(root.val);
preOrder(root.left);
preOrder(root.right);
}
中序遍历：按照左子树–>根节点–>右子树的顺序进行遍历。
public void inOrder(TreeNode root){
if(root == null)
return;
inOrder(root.left);
System.out.println(root.val);
inOrder(root.right);
}
后序遍历：按照左子树–>右子树–>根节点的顺序进行遍历。
public void postOrder(TreeNode root){
if(root == null)
return;
postOrder(root.left);
postOrder(root.right);
System.out.println(root.val);
}
二、递归与非递归算法
遍历算法一般有两种实现方式：递归算法和非递归算法。
递归算法是指在函数中调用函数本身进行实现，递归实现简单，代码清晰，但可能会出现栈溢出的情况，适用于数据规模较小或者深度不大的情况。
public void preOrder(TreeNode root){
if(root == null)
return;
System.out.println(root.val);
preOrder(root.left);
preOrder(root.right);
}
非递归算法是使用自定义栈或队列进行实现，递归转非递归的核心在于使用栈或队列存储节点，每次循环遍历节点时，将其子节点或兄弟节点压入栈或队列。
public void preOrder(TreeNode root){
if(root == null)
return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
System.out.println(node.val);
if(node.right != null)
stack.push(node.right);
if(node.left != null)
stack.push(node.left);
}
}
三、深度优先遍历与广度优先遍历
在树结构中，有两种主要的遍历方式：深度优先遍历（Depth-First-Search，DFS）和广度优先遍历（Breadth-First-Search，BFS）。
深度优先遍历是指从根节点开始，先遍历左分支，再遍历右分支，直到遍历到某个叶子节点为止。
public void dfs(TreeNode root){
if(root == null)
return;
System.out.println(root.val);
dfs(root.left);
dfs(root.right);
}
广度优先遍历是指从根节点开始，按照层次依次遍历每个节点。
public void bfs(TreeNode root){
if(root == null)
return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
System.out.println(node.val);
if(node.left != null)
queue.offer(node.left);
if(node.right != null)
queue.offer(node.right);
}
}
四、总结
Java中实现遍历操作的方式较为灵活，可根据不同的数据结构和场景进行选择。需要注意的是，不同的算法实现对于时间和空间的消耗有所不同，我们需要根据实际情况进行选择。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/245206.html
微信扫一扫 
支付宝扫一扫 