[자료구조] 7일차 트리의 표현 방법, 트리 순회하기

트리의 표현 방법

: 이진 트리의 각 노드는 왼쪽 또는 오른쪽 자식을 갖고 있으므로 위와 같이 표현 가능.

 

 

**** 완전 이진 트리의 경우 배열로 간단하게 구현 ****

• 각 정점에 순서대로 번호를 붙일 수 있다.
• 어떤 정점의 번호가 n이면 왼쪽 자식은 2n, 오른 쪽 자식은 2n + 1
• 배열로 완전 이진트리 표현
•  

트리 순회하기

트리의 모든 노드를 방문하는 순서

• 트리에 들어있는 자료에 접근하기 위해 순회를 해야함.
• 비선형 구조 트리는 정해진 순서가 존재하지 않는다.
• DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 방문 순서로 두가지가 있음.

 

DFS 종류

1. 전위 순회
2. 중위 순회
3. 후위 순회

• DFS는 재귀호출을 사용하는 알고리즘으로, 트리의 재귀적 특성을 알아야함. 스택을 이용한다고 볼 수 있음.

서브 트리

• 기존 트리에서 하위의 트리 구조

트리 순회하기 - DFS

: 정점을 언제 방문하는지에 따라 순서가 달라짐.

: 재귀 호출을 이용하는 기본 개념 자체는 동일함.

*** 전체 트리를 순회하기 위해 서브 트리를 순회한다 ***

→ 순회를 위해 순회한다 = 재귀 호출

 

트리 순회하기 - BFS

: 큐 자료구조를 이용하여 구현

: 이웃한 정점일수록 먼저 방문해야하므로 큐를 이용해야 함.