[자료구조] 트리(Tree)

이진 트리

정의

무방향이면서 사이클이 없는 연결 그래프.

 

특징

• 계층 형태로 이루어져 있고, 최상위 노드를 제외한 모든 노드가 하나의 부모 노드를 가지고 있는 특별한 그래프
• V개의 정점을 가졌을 때, V-1개의 간선을 가지고 있다.
• 임의의 두 점을 연결하는 Simple Path(시작 노드부터 도착 노드까지 중복되는 노드가 없는 경로)가 유일하다.
• 각 노드마다 최대 두 개의 자식을 가질 수 있는 트리를 이진 트리라고 한다.

 

이진 트리의 순회

• 레벨 순회 : 계층 순으로 방문해 나가는 방법. BFS 순회와 동일하다.
• 전위 순회(Preorder Traversal) : 현재 노드 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 방문해 나가는 방법. DFS 순회와 동일하다.
• 중위 순회(Inorder Traversal) : 왼쪽 서브트리 - 현재 노드 - 오른쪽 서브트리 순으로 방문해 나가는 방법.
  • 이진 탐색 트리를 중위 순회할 경우, 크기 순으로 방문하게 된다.
• 후위 순회(Postorder Traversal) : 왼쪽 서브트리 - 오른쪽 서브트리 - 현재 노드 순으로 방문해 나가는 방법.