在Java中,二叉樹的遍歷有三種方式:前序遍歷、中序遍歷和后序遍歷。下面是這三種遍歷方式的代碼示例:
// 定義二叉樹節點
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
// 前序遍歷
void preOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " "); // 先訪問根節點
preOrderTraversal(root.left); // 再前序遍歷左子樹
preOrderTraversal(root.right); // 最后前序遍歷右子樹
}
// 中序遍歷
void inOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
inOrderTraversal(root.left); // 先中序遍歷左子樹
System.out.print(root.val + " "); // 再訪問根節點
inOrderTraversal(root.right); // 最后中序遍歷右子樹
}
// 后序遍歷
void postOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
postOrderTraversal(root.left); // 先后序遍歷左子樹
postOrderTraversal(root.right); // 再后序遍歷右子樹
System.out.print(root.val + " "); // 最后訪問根節點
}
使用時,可以先構建二叉樹,然后根據需要選擇對應的遍歷方法進行遍歷。例如:
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);
// 前序遍歷
System.out.println("前序遍歷結果:");
preOrderTraversal(root);
// 中序遍歷
System.out.println("\n中序遍歷結果:");
inOrderTraversal(root);
// 后序遍歷
System.out.println("\n后序遍歷結果:");
postOrderTraversal(root);
}