코테/자료구조

목차 📍 정의 및 특징 각 노드의 자식 노드(=차수)가 2 이하인 트리 - 어떤 노드를 선택했느냐에 따라 결과가 달라지므로, 항상 같은 결과 보장 X - 시간 복잡도 : O(V + E) #사이클X #방향그래프 📍 종류 ① 편향 이진 트리 ② 포화 이진 트리 - 트리 높이 모두 일정 & 리프 노드 꽉 참 ③ 완전 이진 트리 - 마지막 레벨 제외 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리 📍 순차 표현 - 1차원 ‘배열’ 형태로 표현 - 트리의 노드와 배열의 인덱스 간 상관 관계 ➕ 예제 [백준/JAVA] 1991번: 트리 순회 🔺 문제 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼..

📍 정의 및 특징 사이클이 없다 트리는 그래프 구현 방식을 이용할 수 있고, 탐색 역시 그래프 알고리즘을 사용할 수 있다. - 예 : 이진 트리, 이진 탐색 트리, 힙 📍 트리 관련 알고리즘 종류 - 트리의 순회 (전위, 중위, 후위) - 트리의 레벨 순회 - 트리의 높이 계산 - 트리의 최소 공통 조상(LCA) ➕ 예제 - 트리에서 각 노드의 부모 노드 구하기 [백준/JAVA] 11725번: 트리의 부모 찾기 🔺 문제 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 bono039.tistory.com - 트리에서 리프 노..