비선형 자료구조 (트리)
이번 포스트에서는 트리에 대한 내용과 이진 트리의 순회방법에 대해 포스팅하겠습니다.
트리
트리란, 한개 이상의 노드로 이루어진 유한집합으로 각 노드들은 루트 노드와 나머지 노드들의 분리 집합으로 이루어 집니다. 이때, 각 집합은 하나의 트리이고, 이를 루트의 서브트리라고 부릅니다.
위 설명으로 이루어 볼때, 트리는 재귀적 형태를 띄고 있다는걸 확인할 수 있습니다.
트리는 후에 설명할 그래프 자료구조의 일종으로, 반사관계, 대칭관계, 추이관계 중 추이관계만을 성립하는 관계입니다.
따라서, 트리는 위에서 아래로 일정한 방향으로 진행하는 모양을 띄고 역으로 거슬러서 올라갈 수 없습니다.
이진트리
이진트리는 공집합이거나, 루트와 왼쪽 서브트리, 오른쪽 서브트리로 분리되어 두 개의 이진트리로 구성된 노드의 유한집합을 의미합니다.
이진트리의 레벨이 0부터 시작한다고 가정할 때, 이진트리의 레벨이 i일때, 최대 노드 수는 2^i 로 정의됩니다.
높이또한 0부터 시작한다고 가정할 때, 높이가 h인 이진트리 내 최대 노드 수는 2^(h+1) - 1 로 정의됩니다.
포화이진트리는 모든 레벨에 노드가 가득 차 있는 이진트리를 의미합니다.
완전이진트리는 마지막 레벨을 제외한 모든 레벨에 노드가 가득 차 있으며, 마지막 레벨은 가득 차 있어도 되지만, 가득 차 있지 않은 경우 노드들이 왼쪽부터 오른쪽으로 빈 곳이 없이 채워진 이진트리를 의미합니다.
n개의 노드를 가지는 완전이진트리의 높이는 log2n의 내림 으로 정의됩니다.
이진트리의 순회
이진트리의 순회방법으로는 전위순회, 중위순회, 후위순회, 레벨순회가 있습니다.
전위순회는 루트노드를 방문하고, 왼쪽 서브트리를 방문하고, 오른쪽 서브트리를 방문하는 순서입니다.
중위순회는 왼쪽 서브트리를 방문하고, 루트노드를 방문하고, 오른쪽 서브트리를 방문하는 순서입니다.
후위순회는 왼쪽 서브트리를 방문하고, 오른쪽 서브트리를 방문하고, 루트노드를 방문하는 순서입니다.
레벨순회는 레벨 순으로 노드를 방문하는 방법입니다.
이진트리 순회 구현
먼저 중위순회의 구현입니다.
재귀적으로 왼쪽 서브트리를 방문하고, 루트 노드를 방문하고, 오른쪽 서브트리를 방문하는 순서로 작성합니다.
|
1
2
3
4
5
6
|
void inOrder(Node* p) { //인자로 루트노드를 받습니다.
if(p == nullptr) return;
inOrder(p->left);
cout << p->data << " ";
inOrder(p->right);
}
|
cs |
다음으로 전위순회의 구현입니다.
중위순회와 순서만 바꾸어 작성합니다.
|
1
2
3
4
5
6
|
void preOrder(Node* p) { //인자로 루트노드를 받습니다.
if(p == nullptr) return;
cout << p->data << " ";
preOrder(p->left);
preOrder(p->right);
}
|
cs |
다음으로 후위순회의 구현입니다.
위와 같이 순서만 바꾸어 작성합니다.
|
1
2
3
4
5
6
|
void postOrder(Node* p) { //인자로 루트노드를 받습니다.
if(p == nullptr) return;
postOrder(p->left);
postOrder(p->right);
cout << p->data << " ";
}
|
cs |
마지막으로 레벨순회의 구현입니다.
큐를 이용하여 순회하는 방법으로, 루트노드가 큐에 삽입되고 그 값을 출력과 동시에 큐에서 삭제합니다.
삭제된 루트노드의 자식 노드를 왼쪽부터 오른쪽 방향으로 삽입합니다. 이를 방문이 끝날때 까지 반복합니다.
|
1
2
3
4
5
6
7
8
9
10
|
void levelOrder(Node* p) {
if(p == nullptr) return;
enqueue(p);
while(!isEmpty()) {
p = dequeue();
cout << p->data << " ";
if(p->left != nullptr) enqueue(p->left);
if(p->right != nullptr) enqueue(p->right);
}
}
|
cs |
이렇게 트리와 이진트리, 이진트리의 순회 방법에 대하여 포스팅 해보았습니다.
다음 포스트에서는 이진탐색트리에 대해서 포스팅 하겠습니다.