본문 바로가기

Algorithm

이진트리탐색 - 전위, 중위, 후위

 

  • 전위 순회(Preorder Traversal)
    • 현재 노드 → 왼쪽 서브트리 → 오른쪽 서브트리
    • 출력 순서: 루트 먼저
  • 중위 순회(Inorder Traversal)
    • 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리
    • 출력 순서: 정렬된 순서
  • 후위 순회(Postorder Traversal)
    • 왼쪽 서브트리 → 오른쪽 서브트리 → 현재 노드
    • 출력 순서: 루트 마지막

 

전위 순회(Preorder): 1 2 4 5 3 6 7
중위 순회(Inorder): 4 2 5 1 6 3 7
후위 순회(Postorder): 4 5 2 6 7 3 1

class TreeNode {
int value;
TreeNode left, right;
public TreeNode(int value) {
this.value = value;
left = right = null;
}
}
public class TreeTraversal {
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.left = new TreeNode(6);
root.right.right = new TreeNode(7);
System.out.println("전위 순회(Preorder):");
preorderTraversal(root); // 출력: 1 2 4 5 3 6 7
System.out.println("\n중위 순회(Inorder):");
inorderTraversal(root); // 출력: 4 2 5 1 6 3 7
System.out.println("\n후위 순회(Postorder):");
postorderTraversal(root); // 출력: 4 5 2 6 7 3 1
}
// 전위 순회 (Preorder Traversal)
public static void preorderTraversal(TreeNode node) {
if (node == null) return;
System.out.print(node.value + " ");
preorderTraversal(node.left);
preorderTraversal(node.right);
}
// 중위 순회 (Inorder Traversal)
public static void inorderTraversal(TreeNode node) {
if (node == null) return;
inorderTraversal(node.left);
System.out.print(node.value + " ");
inorderTraversal(node.right);
}
// 후위 순회 (Postorder Traversal)
public static void postorderTraversal(TreeNode node) {
if (node == null) return;
postorderTraversal(node.left);
postorderTraversal(node.right);
System.out.print(node.value + " ");
}
}