순서 트리 탐색

 

전위 순회(Preorder)

노드 방문 ➡ 왼쪽 자식 ➡ 오른쪽 자식

11 ➡ 5 ➡ 4 ➡ 1 ➡ 7 ➡ 6 ➡ 9 ➡ 15 ➡ 13 ➡ 12 ➡ 14 ➡ 18

 

중위 순회(Inorder)

왼쪽 자식 ➡ 노드 방문 ➡ 오른쪽 자식

1 ➡ 4 ➡ 5 ➡ 6 ➡ 7 ➡ 9 ➡ 11 ➡ 12 ➡ 13 ➡ 14 ➡ 15 ➡ 18

 

후위 순회(Postorder)

왼쪽 자식 ➡ 오른쪽 자식 ➡ (돌아와) 노드 방문

1 ➡ 4 ➡ 6 ➡ 9 ➡ 7 ➡ 5 ➡ 12 ➡ 14 ➡ 13 ➡ 18 ➡ 15 ➡ 11

 

---

소스코드

class Node{
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
    }
}

// 전위순회 : 루트 -> 왼쪽 -> 오른쪽
public void preorder(Node root) {
    System.out.print(root.data); // 루트 먼저 출력
    if (root.left != null) preorder(root.left); // 왼쪽 탐색
    if (root.right != null) preorder(root.right); // 오른쪽 탐색
}

// 중위순회 : 왼쪽 -> 루트 -> 오른쪽
public void inorder(Node root) {
    if (root.left != null) inorder(root.left); // 왼쪽 탐색
    System.out.print(root.data); // 루트 먼저 출력
    if (root.right != null) inorder(root.right); // 오른쪽 탐색
}

// 후위순회 : 왼쪽 -> 오른쪽 -> 루트
public void postorder(Node root) {
    if (root.left != null) postorder(root.left); // 왼쪽 탐색
    if (root.right != null) postorder(root.right); // 오른쪽 탐색
    System.out.print(root.data); // 루트 먼저 출력
}