종만북 ch21 트리

트리의 도입

우리가 여태까지 배운 연결리스트나 벡터 배열 등은 모두 자료를 한 줄로 쭉 늘어놓은 형태, 즉 선형적 구조를 가지고 있다.
그러나, 조직도나 대진표와 같이 계층적인 구조를 가진 자료들을 표현해야할 때가 있는데 이때 사용하는 자료구조가 바로 트리이다.

트리의 구성 요소

트리는 저장된 자료(노드)들이 간선으로 연결된 구조이다.
이후에는 최단 거리를 계산하기 위해 이 간선에 가중치를 두는 경우도 있다(크루스칼 알고리즘 등)

자식과 부모

현실세계의 부모 자식 관계와 마찬가지로, 부모가 같은 두 노드는 형제라고 부른다.
참고로 두 연결된 노드 중 상위 노드가 부모 하위 노드가 자식이다.

유의점

자식은 여러 개여도 부모는 단 하나만 가질 수 있다.
그래서 최종적으로는 다른 모든 누드를 자손으로 갖는 단 하나의 노드가 존재하게 되는데 이 노드를 루트라고 부른다.
반대로 자식이 없는 경우 리프라고 부른다.

깊이

트리의 기본적인 구성요소는 아니지만, 따로 설명하기에는 분량이 짧아 구성 요소 파트에 집어넣었다.
깊이는 루트에서 어떤 노드에 도달하기 위해 거쳐야하는 간선의 수를 이야기하며, 깊이가 깊을 수록 노드는 하단에 위치하게 된다.

재귀적 성격

트리는 재귀적인 특성을 갖고 있다.
이는 이진 트리든 다른 종류의 트리든 상관없이, 결국 최종적으로 루트 노드가 존재하게 되기 때문이다.
특정 루트를 통해 탐색을 시작한 후 하나의 가지를 끝내면 다른 가지를 찾는 방식으로 탐색을 이어나가므로, 트리르 다루는 코드들은 대개 재귀 호출을 이용해 구현한다.

트리 탐색하기

트리의 모든 노드들을 방문(탐색)하는 과정을 우리는 트리의 순회라고 부른다.
보통 순회는 트리의 재귀적인 특성을 이용하며, 어디부터 탐색하느냐에 따라 전위순회,준위순회,후위 순회로 나뉜다.

전위순회

전위 순회는 루트 노드 방문 이후 왼쪽 서브 트리->오른쪽 서브 트리의 순서로 순회를 한다.
주로 트리를 복사하거나, 트리의 높이를 구하는 데에 사용한다.

중위순회

중위 순회는 왼쪽 서브 트리->루트 노드->오른쪽 서브 트리의 순서로 순회를 한다.

후위 순회

후위 순회는 오른쪽 서브 트리->루트 노드->왼쪽 서브트리의 순서로 순회를 실시한다.