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中實現遍歷操作的方式較為靈活，可根據不同的數據結構和場景進行選擇。需要注意的是，不同的演算法實現對於時間和空間的消耗有所不同，我們需要根據實際情況進行選擇。