알고리즘 (4): 트리
트리
- 정보를 갖는 노드들의 집합
수직 계층의 자료구조로, 하나의 루트 노드로부터 연결된 여러 노드들은 부모 자식의 관계를 가지며 자기 자신이 부모 노드가 되어 다른 노드를 자식으로서 연결할 수 있다.
루트(Root): 부모를 갖지 않는 최상단 노드
- 자식(Child): 부모 노드에 연결된 노드, 해당 노드에 접근하기 위해서는 부모 노드를 통해 접근해야 한다.
- 형제(Siblings): 같은 부모에 연결된 노드들은 형제 관계를 갖지만 트리 특성상 형제 노드만으로는 접근이 불가능하고 부모노드를 통해서만 접근 가능하다.
- 내부 노드(Internal node): 최소 하나의 자식을 갖는 노드
- 외부 노드(External node, Leaf node): 자식을 갖지 않는 노드
- 조상 노드(ancestor node): 노드의 부모 노드가 루트가 아니라면 해당 부모 노드도 부모 노드를 갖는다. 부모 노드 또한 조상 노드로서 표현됨.
- 깊이(Depth): 루트 노드로부터 자신까지 가는 경로의 길이.
- 레벨(Level): 루트 노드에서 자신까지 가는 경로+1.
- 높이(Height): 트리가 갖는 노드들의 최대 깊이를 의미.
- 차수(Degree): 자식노드가 최대로 가질 수 있는 형제 노드의 수
이진트리(Binary Tree)
- 자식노드가 최대 두개인 노드들로 구성된 트리
내부 노드의 자식들을 좌측 자식, 우측 자식으로 나누어 표현한다.
정 이진 트리(full binary tree): 모든 내부 노드들이 자식을 두 개 갖는 이진 트리
- 완전 이진 트리(complete binary tree): 마지막 레벨을 제외하고 모든 레벨에 노드들이 완전히 채워져 있고 외부 노드의 경우 왼쪽부터 채워진 트리
- 균형 이진 트리(balanced binary tree): 모든 외부노드들이 같은 깊이를 갖거나, 깊이의 차이가 최대 1인 트리
트리 순회
전위 순회(Preorder Traversal)
- 자식 노드에 접근하기 전에 노드를 방문하는 순회 방식
- 자식 노드의 접근은 자식간의 관계에 의해 형성된 순서를 지키며 먼저 방문함
1
2
3
4
5void preOrder(node* v){
visit(v);
preOrder(v->left);
preOrder(v->right);
}
후위 순회(Postorder Traversal)
- 자식 노드에 먼저 접근한 후 자신의 노드를 방문하는 순회방식
- 루트 노드는 최상위 노드이므로 후위 순회에서 가장 마지막에 방문되어진다.
1
2
3
4
5void postOrder(node* v){
postOrder(v->left);
postOrder(v->right);
visit(v);
}
중위 순회
- 좌측 자식 -> 현재 노드 -> 우측 자식의 순으로 노드를 방문하는 순회방식
- 자식 사이에 현재 노드의 방문이 이루어지므로 이진트리가 아닌 경우 임의로 순서를 정하여 순회할 수 있다.
1
2
3
4
5void inOrder(node* v){
inOrder(v->left);
visit(v);
inOrder(v->right);
}
오일러 투어 순회(Euler Tour Traversal)
- 현재 노드 -> 좌측 자식 -> 현재 노드 -> 우측 자식 -> 현재 노드의 순으로 노드를 방문하는 순회방식
- 현재 노드를 먼저 방문하는 전위 순회, 좌측 자식 방문 후 자기 노드를 방문하고 우측 노드를 방문하는 중위 순회, 자식 노드를 방문한 후 자기 노드를 방문하는 후위 순회가 모두 합쳐진 순회방식으로 볼 수 있다.
1
2
3
4
5
6
7
8
9
10
11void eulerTour(node* v){
visit(v);
if(v->left != nullptr){
eulerTour(v->left);
visit(v);
}
if(v->right != nullptr){
eulerTour(v->right);
visit(v);
}
}