hyeoneee's blog

트리를 이해하는 문제이다

이문제는 완전 이진트리를 중위 순회 하는 방법이다

중위 순회는 루트 노드를 중간에 읽는 방법이다

LEFT자식 -> ROOT -> RIGHT 자식

참고로

전위 순회 : ROOT -> LEFT -> RIGHT

후위 순회 : LEFT -> RIGHT ->ROOT

해당 문제에서 input이 이런식으로 들어오므로 input을 받을 때 주의 해야한다.

하지만 완전이진트리에서는 이걸 감안할 필요가 없다 트리에 들어가는 순서가 일정하기 때문이다.

그러므로 index와 value값만 받고 나머지는 무시해준다 ^_^;;

그래서 해당 tree 테이블에 해당 index값에 value값을 넣어주고

그다음 중위 순회 하는 function을 call 해준다.

먼저 해당 function을 나가는 조건을 명시해준다.

1. node가 tree의 수를 벗어나거나

2. tree에 값이 없다

그리고 참고로

tree는 인덱스가 0이 아닌 1부터 시작하도록 설계해주었다

완전이진 트리이므로

그리고 숫자 계산하기도 이게더 편하다.

그리고 먼저 LEFT를 먼저 뽑아줄거니깐

*2를해서 inOrder 메소드를 호출하고

그다음 출력 (ROOT)

그다음 오른쪽 자식 호출 *2+1

전위, 후위 순위는 이 출력하는 라인만 순서만 바꾸어 주면된다

다음은 input , output 파일이다.