1. 트리
- Node와 Edge로 이루어진 자료구조
- 트리는 값을 가진 노드(Node)와 이 노드들을 연결해주는 간선(Edge)로 이루어져있다.
- 그림 상 데이터 1을 가진 노드가 루트(Root) 노드다
- 모든 노드들은 0개 이상의 자식노드를 갖고 있으며 부모-자식 관계로 불린다.
2. 트리 특징
- 트리에는 사이클이 존재 할 수 없다.
- 모든 노드는 자료형으로 표현이 가능하다.
- 루트에서 한 노드로 가는 경로는 유일한 경로 뿐이다.
- 노드의 개수가 N개면, 간선은 N-1 개를 가진다.
3. 트리 순회 방식
- 전위 순회
각 루트를 순차적으로 먼저 방문하는 방식 - 중위 순회
왼쪽 하위 트리를 방문 후 루트를 방문하는 방식 - 후위 순회
왼쪽 하위 트리부터 하위를 모두 방문 후 루트를 방문하는 방식이다 - 레벨 순회
루트부터 계층 별로 방문하는 방식이다.
smilegate