트리
-
트리와 그래프의 관계
-
그래프
그래프는 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조이다.
이를 통해 연결된 노드 간의 관계를 표현할 수 있는 자료구조이다. -
트리
트리는 그래프와 같이 노드와 노드간을 연결하는 간선으로 구성된 자료구조이다.
그러나 트리는 그래프 중에서도 특수한 케이스에 해당하는 자료구조이다.
트리는 두 개의 노드 사이에 반드시 1개의 경로만을 가지며
사이클이 존재하지 않는 방향 그래프이다.
이러한 특성 때문에 '최소 연결 트리'라고 부르기도 한다.
부모-자식 관계가 성립하기 때문에 계층형 모델이라고도 한다.
- 그래프와 트리 비교
출처: https://bigsong.tistory.com/33
이진트리
이진트리란, 모든 노드들이 둘 이하(0,1,2 개)의 자식을 가진 트리이다.
이진탐색트리
왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 이진 트리이다.
순회 종류
1) 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문
뿌리 -> 왼쪽 자식 -> 오른쪽 자식
( 8 -> 1 -> 3 -> 6 -> 4 -> 7 ....)
2) 중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문
왼쪽자식 -> 뿌리 -> 오른쪽 자식
( 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> ...)
3) 후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리(root)를 방문
왼쪽자식-> 오른쪽 자식 -> 뿌리
(1 -> 4 -> 7 -> 6 -> 3 -> 13 -> ..)
이외에도 정 이진트리, 완전 이진트리, 완전 이진 탐색 트리, 포화 이진 트리 등 많은 이진트리 종류가 있다.
출처
