[자료구조] 이진 트리 순회(Traversal)

트리 순회(Traversal)

• 트리의 모든 노드를 한 번씩 방문하는 것을 의미
• 재귀 함수로 구현할 수 있다.

​

예시 트리

 

​

1. 전위 순회 (Preorder Traversal)

• 현재 노드를 먼저 방문
• 현재 노드 방문 -> 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문

    public static void preorder(int index, int tree[])
    {
        if(index < tree.length)
        {
            System.out.println(tree[index]);//현재 노드 출력
            preorder(index*2,tree);
            preorder(index*2+1,tree);
        }
    }

결과 :

1 2 4 5 3 6 7

​

2. 중위 순회 (Inorder Traversal)

• 현재 노드를 중간에 방문
• 왼쪽 서브트리 방문 -> 현재 노드 방문 -> 오른쪽 서브트리 방문

    public static void inorder(int index, int tree[])
    {
        if(index < tree.length)
        {
            inorder(index*2,tree);
            System.out.println(tree[index]);//현재 노드 출력
            inorder(index*2+1,tree);
        }
    }

결과 :

4 2 5 1 6 3 7

​

3. 후위 순회 (Postorder Traversal)

• 현재 노드를 마지막에 방문
• 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문 -> 현재 노드 방문

    public static void postorder(int index, int tree[])
    {
        if(index < tree.length)
        {
            postorder(index*2,tree);
            postorder(index*2+1,tree);
            System.out.println(tree[index]);//현재 노드 출력
        }
    }

결과 :

4 5 2 6 7 3 1