Java实现遍历

一、遍历算法介绍

遍历是指按照一定的顺序，对数据结构中的每个元素均访问一次而进行的操作。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中实现遍历操作的方式较为灵活，可根据不同的数据结构和场景进行选择。需要注意的是，不同的算法实现对于时间和空间的消耗有所不同，我们需要根据实际情况进行选择。