9-1장 트리

1. 트리 정의하기 

 

트리(Tree)

- 데이터 사이의 계층 관계를 나타내는 자료구조 

 

 

루트(root)

- 트리의 가장 윗부분에 위치하는 노드 

- 하나의 트리에는 하나의 루트가 있음

 

리프(leaf)

- 트리의 가장 아랫부분의 위치하는 노드 

- 더이상 뻗어나갈 수 없는 마지막에 위치한 노드 

 

안쪽 노드 

- 루트를 포함하여 리프를 제외한 노드 

 

자식(child)

- 어떤 노드로부터 가지로 연결된 아래쪽 노드 

 

부모(parent)

- 어떤 노드에서 가지로 연결된 위쪽 노드 

 

형제(sibling)

- 같은 부모를 가지는 노드 

 

조상(ancestor)

- 어떤 노드에서 가지로 연결된 위쪽 노드  all

 

자손(descendant)

- 어떤 노드에서 가지로 연결된 아래쪽 노드 all

 

레벨(level)

- 루트로부터 얼마나 떨어져 있는지에 대한 값

 

차수(degree)

- 노드가 갖는 자식의 수 

- 모든 노드의 차수가 n이하인 트리 = n진 트리

 

높이(height)

- 루트부터 가장 멀리 떨어진 리프까지의 거리(리프 레벨의 최댓값)

 

서브 트리(subtree)

- 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리 

 

널 트리 (nulltree)

- 노드,가지가 없는 트리 

 

 

2. 순서 트리와 무순서 트리 정의하기 

 

순서 트리 (ordered tree)

- 형제 노드의 순서가 있는 트리 

 

무순서 트리 (unordered tree)

- 형제 노드의 순서가 없는 트리 

 

 

3. 순서 트리의 탐색 방법 알아보기

 

- 순서 트리의 노드를 스캔하는 방법

 

1) 너비 우선 탐색 (breadth-first Search)

 

- 낮은 레벨에서 시작해 왼쪽에서 오른족 방향으로 검색하고 한 레벨에서의 검색이 끝나면 다음 레벨로 내려감

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

2) 깊이 우선 탐색 (depth - first Search)

 

- 리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법 

- 리프에 도달해 더 이상 검색을 진행할 곳이 없는 경우에는 부모에게 돌아감

 

- 노드 A는 B와 C라는 두개의 자식 노드를 가짐

- 깊이 우선 탐색을 진행하면서 노드 A는  3회 지나감

1. A에서 B로 내려가며 A를 지남
2. B에서 C로 지나가며 A를 지남
3. C에서 A로 되돌아오면서 A를 지남

노드를 지나가는 최댓값 3회

 

- '언제 노드를 방문할지'에 따라 3가지로 구분

 

1)전위 순회(Preorder)

 

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

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

 

2) 중위 순회 (Inorder)

 

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

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

 

3) 후위 순회 (Postorder)

 

- 왼쪽 자식 -> 오른쪽 자식 -> (돌아와)노드 방문

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