이진트리 순회·복원 계산기
이진트리의 전위·중위·후위·레벨 순회를 한 번에 내고, 두 순회에서 트리를 거꾸로 복원합니다. 전위와 후위만으로는 왜 트리가 정해지지 않는지도 실제 예로 확인할 수 있습니다.
왼자식은 2i+1, 오른자식은 2i+2 자리입니다. 빈 자리는 점(.)으로 둡니다.
전위 순회 (뿌리 → 왼쪽 → 오른쪽)
A B D E C F
노드 6개 · 높이 3
A
B C
D E · F
위에서부터 한 층씩
사용 방법
- 1트리를 배열 표현으로 넣습니다. 왼자식은 2i+1, 오른자식은 2i+2 자리이고 빈 자리는 점(.)으로 둡니다.
- 2전위·중위·후위·레벨 순회 결과와 높이·잎 노드 수를 확인합니다.
- 3«두 순회로 복원» 탭에서는 전위+중위 또는 후위+중위를 넣어 트리를 거꾸로 만들 수 있습니다.
- 4복원된 트리에 자식이 하나뿐인 노드가 있으면, 전위+후위만으로는 왜 안 되는지 함께 나옵니다.
자주 묻는 질문
뿌리를 언제 보느냐만 다릅니다. 왼쪽을 오른쪽보다 먼저 보는 것은 셋 다 같고, 뿌리를 앞에 두면 전위(뿌리→왼쪽→오른쪽), 가운데 두면 중위(왼쪽→뿌리→오른쪽), 뒤에 두면 후위(왼쪽→오른쪽→뿌리)입니다. 이름의 전·중·후가 곧 뿌리의 자리입니다.
전위+중위 또는 후위+중위면 하나로 정해집니다. 전위의 첫 값(후위라면 마지막 값)이 뿌리이고, 그 값을 중위에서 찾으면 왼쪽이 왼쪽 서브트리, 오른쪽이 오른쪽 서브트리로 갈리기 때문입니다. 이 일을 양쪽 조각에 되풀이하면 트리가 완성됩니다.
자식이 하나뿐인 노드에서 그 자식이 왼쪽인지 오른쪽인지 가릴 수 없기 때문입니다. 전위 [A, B]와 후위 [B, A]는 «A의 왼자식이 B»인 트리와 «A의 오른자식이 B»인 트리를 똑같이 만듭니다. 이 둘을 가르는 것은 중위뿐이며(BA인지 AB인지), 그래서 복원에는 중위가 반드시 필요합니다.
중위 순회입니다. 왼쪽에 작은 값, 오른쪽에 큰 값을 두는 규칙과 «왼쪽 → 뿌리 → 오른쪽»이 정확히 맞물리기 때문입니다. 8-3-10-1-6-14로 이뤄진 트리를 중위로 훑으면 1, 3, 6, 8, 10, 14가 나옵니다.
되지 않습니다. 중위 순회에서 뿌리 값을 찾을 때 어느 것을 가름점으로 삼을지 정할 수 없어 답이 여러 개가 되기 때문입니다. 그래서 이 계산기는 중복 값이 있으면 계산을 멈추고 알려 줍니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 트리는 배열 표현으로 주고받습니다. 왼자식 2i+1, 오른자식 2i+2, 부모 ⌊(i−1)/2⌋로 자리를 잡으며 빈 자리는 점(.)입니다. 부모 자리가 비었는데 자식에 값이 있으면 트리가 아니므로 거절합니다.
- 한쪽으로 치우친 트리는 깊이 h에 최대 2ʰ−1칸이 필요해 배열이 빠르게 길어집니다. 이 계산기는 그 한계에 닿으면 계산을 멈추며, 배열 표현이 완전이진트리에만 어울린다는 것이 그 이유입니다.
- 높이는 «층수»로 셉니다. 노드가 하나뿐인 트리가 1단입니다. 간선 수로 세는 교재와는 1만큼 차이가 납니다.
- 수식 트리에서는 전위 순회가 전위표기(+ 3 4), 후위 순회가 후위표기(3 4 +)와 같습니다. 중위 순회는 괄호가 없으면 원래 식과 달라질 수 있어 그대로 쓰지 못합니다.
- 레벨 순회는 보통 큐로 구현하지만, 배열 표현에서는 앞에서부터 순서대로 읽는 것과 같습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.