先序遍历是一种深度优先遍历方法,它遵循以下顺序:
1. 访问根节点
2. 遍历左子树
3. 遍历右子树
下面是一个使用递归方法实现先序遍历的Java代码示例:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; left = null; right = null; }
}
public class BinaryTree {
TreeNode root;
// 先序遍历的递归实现
public void preOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.val + " "); // 访问根节点
preOrderTraversal(node.left); // 遍历左子树
preOrderTraversal(node.right);// 遍历右子树
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
System.out.println("先序遍历结果:");
tree.preOrderTraversal(tree.root);
}
}
```
在这个示例中,我们定义了一个`TreeNode`类来表示二叉树的节点,每个节点包含一个整数值和指向左右子节点的指针。`BinaryTree`类包含一个指向根节点的指针和一个`preOrderTraversal`方法,用于递归地进行先序遍历。在`main`方法中,我们创建了一个示例二叉树,并调用`preOrderTraversal`方法来输出先序遍历的结果。
先序遍历的输出结果应该是:`1 2 4 5 3`,这表示先序遍历的顺序是根节点(1),然后是左子树(2 -> 4 -> 5),最后是右子树(3)。