포화 N진 트리에서 단말 노드들 왼쪽 부터 세어 K번째 노드를 찾고자 한다.

이때 루트를 포함하여 경유해야 하는 노드의 수를 구하는 문제를 생각해 보자.

방문하는 순서는 아래와 같은 규칙을 따른다.

1. i 번째 노드를 방문한 후 i를 1증가 시키고, 다시 방문하기를 반복한다. i의 범위는 1 <= i <= N 이 되므로 N + 1은 다시 1이된다. 2. 루트 부터 시작하며 루트의 i =1 이다.

3. 자식노드를 방문할때 방문순서는 i값에 의하여 결정된다. 현재노드가 i라면 다음 방문하는 자식 노드는 왼쪽으로부터 i번째 자식 노드이다.

4. 방문한 단말 노드가 찾는 단말 노드가 아니면 현재 노드의 부모 노드로 돌아간다.

5. 방문한 단말 노드가 찾는 단말 노드이면 종료한다.

예를 들어 높이가 2인 포화 4진 트리가 주어지면 아래 그림과 같이 방문 순서가 결정된다.

트리의 높이 H는 0부터 시작하며 찾고자 하는 단말노드 번호는 1에서부터 N^H 매겨질때,

단말 노드의 번호 K를 찾을 때까지 경유하는 노드의 수를 출력하는 프로그램을 작성하시오.

좀 더 새로운 트리 순회 timer 1s memory 128MB

좀 더 새로운 트리 순회 1s 128MB