트리의 구조와 관련된 용어

루트

• 트리의 가장 위쪽에 있는 노드.
• 루트는 트리 하나에 1개만 존재.

리프

• 가장 아래쪽에 있는 노드
• 단말 노드, 외부 노드라고도 함.
• 물리적으로 가장 밑에 위치 한다는 의미가 아니라 가지가 더이상 뻗어나갈 수 없는 마지막에 노드가 있다는 것!

비단말 노드

• 리프를 제외한 노드

자식

• 어떤 노드와 가지가 연결되었을 때, 아래쪽 노드

부모

• 어떤 노드와 가지가 연결되었을 때, 위쪽에 있는 노드
• 노드의 부모는 하나뿐!

레벨

• 루트에서 얼마나 멀리 떨어져 있는지 나타내는 것.

차수

• 각 노드가 갖는 자식의 수
• 모든 노드의 차수가 n이하인 트리를 n진 트리라 함.
• 위 그림은 모든 노드의 자식이 3개 이하이므로 삼진트리임.
• 모든 노드의 자식이 2개 이하면 이진트리

높이

• 루트에서 가장 멀리 있는 리프까지의 거리 -> 리프 레벨의 최댓값

순서 트리와 무순서 트리

형제 노드의 순서관계가 있는지에 따라 분류.
순서 관계가 있으면 -> 순서 트리
순서 관계가 없으면 -> 무순서 트리

순서 트리의 검색

너비 우선 검색

• 낮은 레벨 부터 왼쪽에서 오른쪽으로 검색, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법

깊이 우선 검색

• 리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 함.
• 리프에 도달해서 더 이상 검색할 곳이 없으면 일단 부모 노드로 돌아가고 그 뒤 다시 자식 노드로 내려감
• 깊이 우선 검색은 세 종류의 스캔 방법으로 구분
  

1. 전위 순회

노드 방문 -> 왼쪽 자식 -> 오른쪽 자식

노드 A의 통과 시점에 주목하면, 'A를 방문->B로 내려감->C로 내려감'의 순서

트리 전체의 스캔

A->B->D->H->E->I->J->C->F->K->L->G

2. 중위 순회

왼쪽 자식 -> 노드 방문 -> 오른쪽 자식

노드 A의 통과 시점에 주목하면 'B로 내려감 -> A를 방문 -> C로 내려감의 순서

트리 전체의 스캔

H->D->B->I->E->J->A->K->F->L->C->G

3. 후위 순회

왼쪽 자식 -> 오른쪽 자식 -> 노드 방문

노드 A의 통과 시점에 주목하면 'B로 내려감 -> C로 내려감 -> A를 방문'의 순서

트리 전체의 스캔

H->D->I->J->E->B->K->L->F->G->C->A