前序遍历Pre-order Traversal
前序遍历Pre-order Traversal
定义
前序遍历（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
这个实现遵循了“根-左-右”的顺序，并使用递归来确保遍历整个树。注意，如果树的某个节点（或整个树）是空的，则不会对其进行遍历。
腾讯云开发者
