트리(Tree)
트리(Tree)
나무의 형태를 뒤집은것과 같은 형태의 자료구조이다.
일반적으로 트리의 최상단노드를 루트노드(Root node)라고 하고 가지로 인해 노드가 연결되는 것을 확인할 수 있다.
트리에서 가장 마지막 끝에 해당하는 노드들을 리프노드(Leaf node)라고 한다.
각 노드들은 부모자식관계를 갖게 된다.
상위노드가 부모노드, 하위노드가 자식노드가 되며 자식노드가 여러개라면 형제노드라고 한다.
트리에서 길이란 출발노드에서 목적지 노드까지 거쳐야 하는 가지수를 의미한다.
예를 들어 루트노드에서 목적 노드까지 가는데 한개의 노드를 거쳐간다면 가지의 수가 2개이기 때문에 길이는 2가된다
깊이란 루트노드에서 특정노드까지의 길이를 의미한다.
루트노드의 바로 하위노드는 깊이가 1이고 그 아래 노드는 깊이가 2가 된다.
이진트리(Binary Tree)
최대 2개의 자식을 가질 수 있는 트리이다.
구현이 간단하다는 점에서 다방면으로 활용이 되는 자료구조중 하나이다.
포화이진트리(Full Binary Tree)
리프노드를 제외한 모든 노드가 두 자식을 갖고 있는 트리이다.
완전이진트리(Complete Binary Tree)
모든 노드들이 왼쪽 자식부터 차근차근 채워진 트리다. 왼쪽에서부터 채워져있는 트리를 의미한다.
높이균형트리(Height Balanced Tree)
왼쪽 자식 트리와 오른쪽 자식트리의 높이가 1이상 차이나지 않는 트리이다.
이진 트리는 많은 양의 노드를 낮은 높이에서 관리할 수 있다는 점에서 데이터 활용의 효율성이 높아진다.
데이터 저장, 탐색 등의 다양한 목적에서 사용할 수 있다.
구현 및 순회
이진트리는 포인터를 이용하여 구현하면 효과적인 데이터 관리가 가능하다.
이진트리의 순회
이진트리에 담긴 데이터를 하나씩 방문하는 방법으로 대표적인 세가지 방법이 있다.
전위순회(preorder)
루트에서 출발했을 때 상위노드를 출력하고 왼쪽 하위노드를 출력한다음 오른쪽 하위노드를 출력한다.
위 그림을 보면 root인 30을 먼저 출력한다. 순서가 상위 - 왼쪽 - 오른쪽이기 때문에 왼쪽 하위노드로 먼저
내려간다. 그래서 17을 출력해주고 17의 하위노드중 왼쪽에 있는 5을 먼저 출력 한 다음 23을 출력해준다.
더 하위노드는 없기 때문에 23을 출력한 다음에는 루트의 오른쪽방향으로 내려가서 같은 형태로 48 - 37 -
50을 출력한다.
만약 제일 왼쪽 리프노드인 5에 하위노드로 하나 더 있었다면 5와 23사이에 그 노드가 출력이 된다.
중위순회(inorder)
왼쪽 하위노드를 출력하고 상위노드를 출력 그다음 오른쪽 하위노드를 출력한다.
왼쪽 하위노드를 먼저 출력하는 형태이기 때문에 5을 가장 먼저 출력하고 상위노드인 17을 출력.
그 다음 오른쪽 하위노드인 23을 출력한다. 그럼 루트노드를 기준으로 왼쪽 노드들은 모두 출력했으니 루트노드를
출력해주고 오른쪽 최하단 노드들 중에서 가장 왼쪽에 있는 37부터 시작하여 같은 형태로 출력해준다.
후위순회(postorder)
왼쪽 자식노드를 출력한다음 오른쪽 자식노드를 출력하고 부모노드를 출력한다.
중위순회와 마찬가지로 왼쪽 최하위 노드부터 시작한다. 왼쪽 - 오른쪽 - 상위 순서이기 때문에 5를 출력한 다음
23을 출력하게 되고 상위노드인 17을 출력한다. 그럼 루트노드 기준으로 왼쪽 하위노드들은 모두 출력이 끝났으니
오른쪽 하위노드들을 출력해줘야 한다.
오른쪽 하위노드들 중 왼쪽 최하단 노드인 37로 넘어가고 여기서부터 같은 형태로 출력하며 마지막에 루트노드를
출력하며 마무리된다.
예제코드
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int data;
struct Node* leftChild;
struct Node* rightChild;
} Node;
Node* initNode(int data, Node* leftChild, Node* rightChild){
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->leftChild = leftChild;
node->rightChild = rightChild;
return node;
}
void preorder(Node* root){
if(root){
printf("%d ", root->data);
preorder(root->leftChild);
preorder(root->rightChild);
}
}
void inorder(Node* root){
if(root){
inorder(root->leftChild);
printf("%d ", root->data);
inorder(root->rightChild);
}
}
void postorder(Node* root){
if(root){
postorder(root->leftChild);
postorder(root->rightChild);
printf("%d ", root->data);
}
}
int main(void){
Node* n7 = initNode(50, NULL, NULL);
Node* n6 = initNode(37, NULL, NULL);
Node* n5 = initNode(23, NULL, NULL);
Node* n4 = initNode(5, NULL, NULL);
Node* n3 = initNode(48, n6, n7);
Node* n2 = initNode(17, n4, n5);
Node* n1 = initNode(30, n2, n3);
preorder(n1);
printf("\n");
inorder(n1);
printf("\n");
postorder(n1);
system("pause");
return 0;
}결과값
30 17 5 23 48 37 50
5 17 23 30 37 48 50
5 23 17 37 50 48 30
initNode로 데이터를 넘겨 트리구조를 먼저 만들어 준다.
n1까지 모두 처리하면 위와 같은 형태의 트리구조가 생긴다.
여기서 preorder, inorder, postorder 형태로 출력했을 때의 결과값이 출력이 된다.
preorder에서 보면 root의 data를 제일 먼저 출력한다. 그럼 30이 출력이 되고 그 다음 preorder에 leftChild를
넘겨준다. root에 leftChild가 넘어가니까 n1의 leftChild인 n2를 받아서 출력하고 17이 출력된다.
그럼 또 leftChild가 존재하니까 넘겨주고 n4를 넘겨줘서 5를 출력. n4는 하위노드가 없기 때문에 다시 root가
n2인 형태로 돌아온다. 그럼 rightChild를 넘겨주는 preorder를 처리해서 23을 출력하고 역시 하위노드가
없으므로 n2로 돌아간다. 그럼 n2는 모든 코드를 처리했으므로 n1으로 돌아가고 n1에서는 rightChild를
처리하도록 한다. 그리고 왼쪽 노드들을 출력한 방식과 동일하게 출력해 나가는 것이다.
inorder는 왼쪽 최하단 노드먼저 출력하고 상위노드, 그다음 오른쪽 노드를 출력하므로 preorder와 형태는 같지만
출력문이 leftChild와 rightChild를 넘겨주는 사이에서 처리된다.
inorder로 leftChild를 넘겨주는 형태로 최하단까지 출력없이 계속 내려가기만 하고 최하단 노드에 도착했을 때부터
출력한다.
postorder 역시 왼쪽 최하단 노드가 시작점이기 때문에 inorder와 마찬가지로 leftChild를 넘겨 처리함으로써
왼쪽 최하단 노드로 내려간다. 그리고 오른쪽 노드를 출력한다음 상위노드를 출력해야 하니 오른쪽 노드들을
출력하도록 rightChild를 넘겨주고 제일 마지막에 상위노드를 출력하게된다.
레퍼런스
패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직