안 쓰던 블로그

관련 문제 -이진 검색 트리: www.acmicpc.net/problem/5639 (전위->이진트리) -완전 이진 트리: www.acmicpc.net/problem/9934 (중위->이진트리) 이진 검색 트리 문제부터 본다 전위 순회한 결과 값으로 후위 순회하는 문제이다 전위 순회는 루트-왼쪽-오른쪽 순으로 방문한다 이진 트리는 들어온 값을 루트부터 시작하여 값이 큰지 작은지 비교, 왼쪽/오른쪽 어느 서브 트리로 보낼지를 결정해야 한다 이 문제에서 전위 순회 결과로 이진트리를 만드는 작업은 다음과 같이했다(참고: www.acmicpc.net/problem/1539 ) 1. 전위 순회는 무조건 첫 값이 루트이므로 첫 값은 루트로 넣는다 2. 값을 하나 입력 받는다 3. 현재 노드를 나타낼 now변수를 둔다..

트리 원소들 간에 1:n 관계를 가지는 비선형 자료구조 원소들 간에 계층 관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양 구조 노드: 트리의 원소 -트리 A의 노드: A,B,C,D,E,F,G,H,I,J,K,L 루트 노드: 트리의 시작 노드, 레벨0 -트리 A의 루트 노드: A 간선: 노드를 연결하는 선, 부모-자식 노드 연결 형제 노드: 같은 부모 노드의 자식 노드들 -B,C,D는 형제 노드 조상 노드: 간선을 따라 루트 노드까지 경로에 있는 모든 노드들 -K의 조상 노드: F, B, A 서브 트리: 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 -각 노드는 자식 노드의 개수 만큼 서브 트리를 가짐 -D를 부모로 가지는 H,I,J는 D라는 서브 트리 자손 노드..