15. 트리의 활용(Uses of Tree)

 

15. 1. 이진트리의 순회(Traversal of Binary Tree)

 

- 순회(Traversal): 모든 노드에 한 번씩 방문하는 방법.

 

  1) 항상 Root Node에서 출발한다.

 

  2) 노드의 데이터를 읽기 전에 노드가 존재하는지 먼저 탐색한다.

 

  3) 형제노드 중 항상 왼쪽노드를 먼저 탐색한다.

 

 

- 전위 순회(Preorder Traversal): Parent Node -> Left Child Node -> Right Child Node순으로 탐색.

 

- 중위 순회(Inorder Traversal): Left Child Node -> Parent Node -> Right Child Node순으로 탐색.

 

- 후위 순회(Postorder Traversal): Left Child Node -> Right Child Node -> Parent Node순으로 탐색.

 

 

- 이진탐색트리(Binary Search Tree): 노드가 가지는 데이터에 대한 기준을 가지고 노드의 위치를 탐색할 수 있는 트리.

 

  1) 트리의 모든 노드는 서로 다른 유일키(Data)를 갖는다.

 

  2) 왼쪽에 있는 노드는 그 부모노드의 키보다 작거나 앞선 값을 갖는다.

 

  3) 오른쪽에 있는 노드는 그 부모노드의 키보다 크거나 뒤의 값을 갖는다.

 

---

 

15. 2. 트리의 활용(Uses of Tree)

 

- 신장트리(Spanning Tree): Graph의 모든 꼭짓점을 노드로 포함하는 트리.

 

  1) Spanning Tree의 Root Node는 그래프에 포함된 노드들 중 어떤 것이든 될 수 있다.

 

  2) 그래프에서 노드와 노드간에 모서리가 존재해야만 Parent-Child 관계를 가질 수 있다.

 

- 최소신장트리(Minimal Spanning Tree): Graph의 모든 꼭짓점을 노드로 포함하면서 노드 간의 비용을 최소로 하는 트리.

 

- Minimal Spanning Tree를 만드는 방법으로 프림 알고리즘(Prim Algorithm), 크루스칼(Kruskal Algorithm)을 활용한다.

 

---