遍历树数据结构与递归

考虑具有 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
        }
    }

如上所述,使用递归我们可以遍历树数据结构,而无需使用迭代方法无法实现的任何其他数据结构。