트리 구조
트리는 선형적인 데이터는 아니지만 데이터끼리 부모와 자식들로 연결된 계층적 구조이다.
트리에 대한 용어들은 루트(root) , 차수(degree), 깊이(depth), 높이(height), leaf node, level, sub tree이 있다.
root는 트리의 처음 볼 위치로 어디서든 기준을 잡고 볼 수 있다.
degree는 특정 노드를 기준으로 자식의 수가 얼마나 되는지를 나타낸다
depth는 루트노드와 얼마나 떨어져있는지를 나타낸다. 루트노드에서의 특정 노드 사이의 간선의 개수이다.
height는 트리에서 깊이가 가장 깊은 것의 깊이를 나타내거나 +1 한 것을 나타낸다 height의 시작을 1 또는 0으로 할 수 있기 때문
leaf node는 자식이 없는 노드들을 말한다.
subtree는 부모와의 연결을 끊었을 경우 생기는 트리를 말한다.
트리에서 좀 더 탐색이 쉽고 정형화되어 있는 구조가 있는데 이진트리라고 한다
이진트리는 자식이 최대 2명인 트리를 말한다.
이진트리는 배열로도 구현할 수 있다.
가장 최 상단 루트를 배열 인덱스 1에서 시작한다면
쉽게 배열로 구현할 수 있다.
자식 노드로의 인덱스 접근은 부모노드 인덱스 * 2를 할 경우 왼쪽 자식으로 접근이 가능하고, 부모노드 인덱스 * 2 + 1를 할 경우 오른쪽 자식으로 접근이 가능하다.
이런 트리를 탐색하는 방법이 있는데
전위탐색, 중위탐색, 후위탐색이 있다.
탐색 시에는 재귀함수를 이용하여 탐색하게 된다. 전위, 중위, 후위에 따라 어디에서 재귀함수를 시작할지 다른 것이 특징이다.
전위 탐색 - Pre-order
부모 -> 왼쪽 자식-> 오른쪽 자식 순으로 탐색하는 방법
10 -> 17 -> 25 -> 30 -> 20 -> 42 -> 50
10도 부모이고 왼쪽 자식 갔을 때 17도 부모이다 그리고 왼쪽 오른쪽 가게되는 방식
void preOrder(node_t n)
{
//n은 루트이다.
if(n != NULL){
cout >> n.data;
preOrder(n.left);
preOrder(n.right);
} else {
return;
}
}
중위 탐색 - In-order
왼쪽 자식-> 부모 -> 오른쪽 자식 순으로 탐색하는 방법
25 -> 17-> 30 -> 10 -> 42 -> 20 -> 50
처음 17로 내려가도 왼쪽 자식이 존재한다. 왼쪽 자식 후 부모 그 다음 오른쪽
void inOrder(node_t n)
{
//n은 부모노드이다.
if(n != NULL){
inOrder(n.left);
cout >> n.data; // 부모 접근 시 데이터 처리
inOrder(n.right);
} else {
return;
}
}
후위 탐색 - Post-order
왼쪽 자식-> 오른쪽 자식 -> 부모 순으로 탐색하는 방법
25 -> 30 -> 17 -> 42 -> 50 -> 20 -> 10
void postOrder(node_t n)
{
//n은 부모노드이다.
if(n != NULL){
postOrder(n.left);
postOrder(n.right);
cout >> n.data;
} else {
return;
}
}