늦깍이 코린이

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net Remind Binary Tree Binary Tree란 무엇인가? 각 부모 노드가 최대 두 개의 자식 노드를 가지는 자료구조 각각의 자식 노드는 왼쪽, 오른쪽이라고 명시하기 때문에, 일반적인 트리 구조가 아님! 전위 순회, 후위 순회, 중위 순회 루트 노드부터 모든 노드를 어떻게 방문하는 순서 (부모(1) - 왼쪽 자식(2) - 오른쪽 자식(3)) 전위 순회 : (1) - (2) - ..

학교 수업 '자료구조' 복습입니다. Binary Tree 구현(Link를 사용한 Implementation) 방법 1 : 리프 노드와 내부 노드를 똑같이 구현한다. interface BinNode { E getItem(); BinNode left(); BinNode right(); } 해당 방법으로 구현시, null 값의 개수가 node의 개수 + 1 개 이다. 방법 1의 space overhead *space overhead란? total space(사용 메모리의 총량) - data space(담고자하는 데이터를 위한 메모리 사용량) 위 그림) 데이터 A,B,C,D,E,F,G,H,I -- 9개의 data space total space -- 9 * data + 9 * 2 * pointer space o..

학교 수업 '자료구조' 복습입니다. Binary Trees란? 이진 트리의 정의 각 노드가 자식 노드를 최대 두 개까지만 가지는 트리. 두 자식 노드는 각 각 왼쪽 자식, 오른쪽 자식이라고 부름. *왼쪽, 오른쪽이라고 위치를 명시하기 때문에, 같은 두 개의 자식을 가지고 있는 트리라도 일반적인 트리와 이진 트리는 서로 다름. 정 이진 트리 full binary tree : 각 노드의 자식 노드 수가 2 또는 0인 트리 완전 이진 트리 complete binary tree : 가장 깊은 레벨을 제외한 모든 레벨이 가득 차 있음 마지막 레벨의 노드들은 가능한 왼쪽에 존재 포화 이진 트리 perfect binary tree : 모든 단말 노드의 레벨이 같음 모든 내부 노드의 자식의 수가 2임 Q1) 포화 이진..