前序遍历Pre

定义

前序遍历（Pre-order Traversal）：首先访问根节点，然后递归地访问左子树，最后递归地访问右子树。

示例

假设我们有以下二叉树图例：

          1
         / \
        2   3
       / \   \
      4   5   6
     / \
    7   8
   /
  9

现在，我们将按照前序遍历的步骤来分析这个二叉树： 访问根节点：首先，我们访问根节点，即节点1。 输出序列（目前）：1 递归访问左子树：接下来，我们递归地遍历左子树。左子树的根节点是2。 访问左子树的根节点2。 输出序列（目前）：1 2 递归访问节点2的左子树。左子树的根节点是4。 访问节点4。 输出序列（目前）：1 2 4 节点4有一个左子节点7和一个右子节点8，所以我们继续递归遍历。 访问节点7。 输出序列（目前）：1 2 4 7 节点7有一个左子节点9，继续递归。 访问节点9。 输出序列（目前）：1 2 4 7 9 节点9没有子节点，返回上一层遍历节点8。 访问节点8。 输出序列（目前）：1 2 4 7 9 8 节点的4左右子树都已遍历完毕，返回上一层遍历节点5。 访问节点5。 输出序列（目前）：1 2 4 7 9 8 5 节点5没有左右子节点，左子树的遍历结束。 递归访问右子树：最后，我们递归地遍历右子树。右子树的根节点是3。 访问右子树的根节点3。 输出序列（目前）：1 2 4 7 9 8 5 3 节点3有一个右子节点6，继续递归遍历。 访问节点6。 输出序列（最终）：1 2 4 7 9 8 5 3 6 节点6没有左右子节点，右子树的遍历结束。 遍历结果：按照“根-左-右”的顺序访问的节点序列是 1 2 4 7 9 8 5 3 6。 通过这个过程，我们可以看到前序遍历确保了我们首先访问根节点，然后遍历其左子树，最后遍历其右子树。在遍历左子树和右子树时，我们又分别遵循了相同的“根-左-右”顺序。这种递归的遍历方式能够确保我们按照正确的顺序访问所有的节点，即使树的结构非常复杂。

Java实现示例

在Java中，我们可以使用递归的方式来实现二叉树的前序遍历。首先，我们需要定义一个二叉树节点的类（如果还没有的话），然后实现前序遍历的递归方法。

以下是一个简单的Java实现示例：

// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTreeTraversal {
    
    // 前序遍历（根-左-右）
    public static void preOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        
        // 访问根节点
        System.out.print(root.val + " ");
        
        // 递归遍历左子树
        preOrderTraversal(root.left);
        
        // 递归遍历右子树
        preOrderTraversal(root.right);
    }

    public static void main(String[] args) {
        // 构建题目中的二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(8);
        root.left.left.left.left = new TreeNode(9);

        // 执行前序遍历
        preOrderTraversal(root);
    }
}

当运行上述main方法时，控制台将输出：

1 2 4 7 9 8 5 3 6

这个实现遵循了“根-左-右”的顺序，并使用递归来确保遍历整个树。注意，如果树的某个节点（或整个树）是空的，则不会对其进行遍历。