![]()
문제 링크 : https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 문제 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력 첫째 줄에 프리오더를 출력한다. 풀이 이 문제는 우선 전..
![]()
이진 탐색트리란? 이진 탐색트리는 다음과 같은 속성이 있는 자료 구조이다. 각 노드에 값이 있고, 각 노드마다 최대 두 개의 자식을 갖는다. 왼쪽 자식은 부모보다 키 값이 작고, 오른쪽 자식은 부모보다 키 값이 크다. 이진 탐색트리 예시 {8,3,10,1,6,14,4,7,13} 이 노드를 기준으로, 루트 8 의 왼쪽 서브트리는 3부터 그 이하의 노드들로 이루어진 트리이고, 루트 8 의 오른쪽 서브트리는 10부터 그 밑에있는 노드들로 이루어진 트리이다. 이진 탐색 트리는 유일하지 않다. 예를 들어 {1, 2, 3, 4}에 대한 이진 탐색 트리는 이런식으로 두가지 이상으로 표현 가능하다. 만약 어떤 키 값이 자주 접근될 지 모른다면, 균형잡힌 오른쪽 트리가 유리할 것이고, 만약 1 값이 가장 자주 접근된다면..
