•
트리(Tree)는 그래프에 포함되는 개념이며, 따라서 그래프의 특별한 경우라고 할 수 있다.
1. 트리란?
•
트리(Tree)란 노드가 N개이고, 간선이 N-1개인 그래프이며, 모든 노드가 서로 연결되어 있는 구조이다.
•
대부분의 트리는 루트 노트(root node)가 존재하며, 이러한 트리를 루트 트리(rooted tree)라고 한다.
루트 노트(root node)란 트리를 대표하는 노드로, 트리의 시작 노드를 의미한다.
•
트리인 경우의 예시
◦
간선의 개수가 노드의 개수 - 1개이며, 모든 노드는 서로 연결되어 있다.
•
트리가 아닌 경우의 예시
◦
간선의 개수가 노드의 개수 - 1개이지만, 노드 D가 다른 노드들과 연결되어 있지 않다.
•
트리의 특징
◦
간선의 개수 = 노드의 개수 - 1
◦
모든 노드들이 서로 연결되어 있다.
사이클이 존재하지 않는다.
2. 이진 트리란?
•
이진 트리(binary tree)는 루트 노드(root node)가 존재하면서, 최대 2개의 자식 노드까지만 가지는 루트 트리(rooted tree)이다.
•
이진 트리의 순회 방법 3가지
1.
전위 순회 (pre-order traversal)
부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드
2.
중위 순회 (in-order traversal)
왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드
3.
후위 순회 (post-order traversal)
왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드
2.1. 전위 순회 구현
•
루트 노드에서 시작하여, 부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순으로 방문하면 된다.
예제 코드
2.2. 중위 순회 구현
•
루트 노드를 시작으로, 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드 순으로 방문하면 된다.
예제 코드
2.3. 후위 순회 구현
•
루트 노드를 시작으로, 왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드 순으로 방문하면 된다.
예제 코드