트리
- 트리는 노드들의 집합으로 이루어진 자료구조
- 트리는 하나의 루트 노드를 갖음
- 루트 노드는 0개 이상의 자식 노드를 갖고 있음
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의됨
- 트리 구조는 그래프의 일종
트리에서 사용되는 용어
- 조상 노드 : 선택된 노드에서 루트 노드까지 연결된 모든 노드들
- 후손 노드 : 선택된 노드의 하위(루트 노드 반대방향)에 있는 모든 노드들
- 리프 노드 : 자식이 없는 노드
- 서브 트리 : 트리에서 트리의 형태를 갖춘 일부 노드 집합
- 차수 : 선택된 노드의 자식 노드의 개수
- 깊이 : 루트 노드부터 선택된 노드까지 연결된 선의 개수
- 높이 : 깊이나 최대값과 동일
이진트리 (Binary Tree)
: 이진 트리는 트리를 구성하는 모든 노드의 차수가 2이하인 트리
완전 이진 트리 (Complete Binary Tree)
: 가장 깊은 깊이를 제외하고 모든 깊이마다 노드가 모두 존재해야하며, 가장 깊은 깊이에서 모든 노드들은 왼쪽부터 채워야 함
이진 탐색 트리 (Binary Search Tree)
: 부모 노드를 기준으로 왼쪽 서브 트리와 오른쪽 서브 트리 모두 이진 탐색 트리. 부모 노드를 기준으로 왼쪽 서브 트리의 각 노드의 값은 부모 노드의 값보다 작거나 같음. 부모 노드를 기준으로 오른쪽 서브 트리의 각 노드의 값은 부모 노드의 값보다 큼
문제
[백준] 5639번 : 이진 검색 트리
문제 www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수
lin-ing-link.tistory.com
[백준] 9934번 : 완전 이진 트리
//완전 이진 트리 int re[12][1101]; int input[1024]; void print(int k){ for(int i=0;i<(pow(2,k)-1);++i){ for(int j=0;j > k; for(int i = 0;i<(pow(2,k) - 1);++i){ cin >> input[i]; } print(k); for(int i..
lin-ing-link.tistory.com
반응형
'CS > 자료구조' 카테고리의 다른 글
| [자료구조] map 컨테이너_C++ (0) | 2021.01.23 |
|---|---|
| [자료구조]이진 힙 (Binary Heap) (0) | 2021.01.12 |
| [자료구조] queue 컨테이너_C++ (0) | 2020.12.17 |
| [자료구조] stack 컨테이너_C++ (0) | 2020.12.17 |
| [자료구조] list 컨테이너_C++ (0) | 2020.12.16 |