遍歷樹資料結構與遞迴

考慮具有 3 個成員資料的 Node 類,左子指標和右子指標,如下所示。

public class Node {
    public int data;
    public Node left;
    public Node right;
    
    public Node(int data){
        this.data = data;
    }
}

我們可以遍歷通過連線多個 Node 類的物件構造的樹,如下所示,遍歷稱為樹的按順序遍歷。

public static void inOrderTraversal(Node root) {
        if (root != null) {          
            inOrderTraversal(root.left); // traverse left sub tree
            System.out.print(root.data + " "); // traverse current node
            inOrderTraversal(root.right); // traverse right sub tree
        }
    }

如上所述,使用遞迴我們可以遍歷樹資料結構,而無需使用迭代方法無法實現的任何其他資料結構。