[자료구조] 트리 개념 및 순회 방법, 전위순회, 중위순회, 후위순회

트리

트리는 비선형 자료구조로 노드로 구성되어 있습니다. 노드들이 링크(선)를 통해 연결되어 있으며 계층적 구조를 나타내고자 할때 사용됩니다.

아래의 트리 그림을 가지고 하나하나 기본적인 설명을 하도록 하겠습니다.

⊙루트노드 (root) : 트리의 가장 위, 즉 최상위 노드를 말합니다. 트리에서 가장 중요한 노드입니다. 여기서 A가 루트노드입니다.

⊙잎 또는 단말 노드 (leaf) : 트리의 가장 끝자락에 위치한 노드입니다. 위 트리에서는 G, H, E, I, J가 해당됩니다.

⊙부모노드 (parent) : 현재노드의 한단계 위 계층에 있는 노드를 말합니다. I의 부모노드는 F, C의 부모노드는 A입니다. 

⊙형제노드 (sibling) : 부모가 같은 노드를 의미합니다. D의 형제노드는 E, G의 형제노드는 H입니다.

⊙내부노드 (internal) : leaf가 아닌 노드를 의미합니다.

⊙노드 깊이 (depth) : 루트에서 시작해서 얼마나 깊이 들어가야 그 노드를 만날 수 있는지를 깊이라고 합니다. 기준이 루트노드이므로 A의 깊이는 0, C의 깊이는 1, H의 깊이는 3입니다.

⊙노드 레벨 (level) : 같은 깊이를 갖는 노드의 집합입니다. 단, 깊이와는 다르게 1부터 시작합니다. 레벨 1의 노드는 A, 레벨 2의 노드들은 B, C, 레벨 3의 노드들은 D, E, F가 되겠죠.

⊙트리 높이 (height) : 가장 긴 깊이를 의미합니다. 위 트리의 높이는 3이 됩니다. 트리 높이는 트리에서 가장 중요한 요소인데, 노드의 갯수만큼 높이가 커지면 linkedlist와 성능이 같게 되죠. 그래서 높이가 트리에서 성능을 좌우합니다.

⊙노드 차수 (degree) : 각 노드에서 나가는 선을 의미합니다. 즉, 가지수를 말하겠죠? A의 차수는 2, C의 차수는 1이 됩니다.

⊙트리의 차수 :  가장 큰 차수를 갖고 있는 노드의 차수가 됩니다. 위의 트리에서는 2보다 큰 차수는 없으니, 트리의 차수는 2가 됩니다.

트리의 노드가 N이라고 할때 가지수는 무조건 N-1이 됩니다. 왜냐면 트리에서는 사이클이 존재하지 않기 때문인데, 위 트리에서 노드와 노드사이에 선을 한개만 더 추가하게 되면 사이클이 발생합니다. 특정 노드와 노드사이를 계속 돌 수 있다는 이야기죠. 그러니, 사이클이 발생하는 트리는 없습니다.

트리 순회

트리에는 크게 세가지의 순회 방법이 있습니다. 그 노드를 어떤 순서로 방문하느냐에 따라서 달라집니다. 그 전에 트리를 구현하는 방법을 알아보아야겠죠?

노드가 어떤 식으로 구성되어 있는 지 잠깐만 살펴보겠습니다.

typedef struct node {
	char data;
	struct node *left;
	struct node *right;
} Node;

각 노드는 data라는 변수를 갖고 있습니다. 이 data의 변수는 위 그림에서 알파벳을 저정하고 있습니다.

그리고 left는 그 노드의 왼쪽 자식 노드, right는 그 노드의 오른쪽 자식노드를 의미합니다. 가장 끝에 있는 노드는 left와 right가 NULL이라는 점입니다.

위 트리를 3가지 순회방법인 전위순회, 후위순회, 중위순회 순으로 탐색해봅시다

전위순회(preorder traversal)

전위순회는 현재 노드를 가장 먼저 방문합니다. 그러니 왼쪽 자식과 오른쪽 자식을 현재 자식보다 나중에 방문합니다.

위 그래프를 전위순회로 방문하게 된다면 

A -> B -> D -> G -> H -> E -> C ->F ->I -> J

순으로 트리가 방문됩니다.

void preorder(Node *node) {
	if (node == NULL) return;
	printf(" %c ", node->data);
	preorder(node->left);
	preorder(node->right);
}

후위순회(postorder traversal)

이름에서부터 짐작하셨겠지만 현재 노드를 가장 나중에 방문하는 방식의 순회입니다. 그러니 왼쪽 자식, 오른쪽 자식 노드를 우선적으로 방문합니다.

그러니 후위순회의 결과는

G -> H -> D -> E -> B ->I -> J -> F -> C -> A

입니다.

void postorder(Node *node) {
	if (node == NULL) return;
	postorder(node->left);
	postorder(node->right);
	printf(" %c ", node->data);
}

중위순회(inorder traversal)

우선 왼쪽 자식을 방문하고, 현재 노드를 방문합니다. 그리고 나서 오른쪽 자식 노드를 방문하게 됩니다. 현재 노드를 중간에 방문한다고 해서 중위순회가 됩니다.

방문 순서는 이렇습니다.

G -> D -> H -> B -> E -> A -> C ->I -> F -> J

void inorder(Node *node) {
	if (node == NULL) return;
	inorder(node->left);
	printf(" %c ", node->data);
	inorder(node->right);
}

전체코드

전체코드는 아래와 같습니다. 위의 트리를 그대로 코드로 옮긴거죠. 입력받으면서 동적으로 할 수도 있겠지만 그런 귀찮은 부분까지는 고려하지 않았습니다. 여러분들이 더 잘하실테니까요.

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
	char data;
	struct node *left;
	struct node *right;
} Node;

Node *createNode(char data) {
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}
void preorder(Node *node) {
	if (node == NULL) return;
	printf(" %c ", node->data);
	preorder(node->left);
	preorder(node->right);
}

void postorder(Node *node) {
	if (node == NULL) return;
	postorder(node->left);
	postorder(node->right);
	printf(" %c ", node->data);
}

void inorder(Node *node) {
	if (node == NULL) return;
	inorder(node->left);
	printf(" %c ", node->data);
	inorder(node->right);
}


int main() {
	Node *A = createNode('A');
	Node *B = createNode('B');
	Node *C = createNode('C');
	Node *D = createNode('D');
	Node *E = createNode('E');
	Node *F = createNode('F');
	Node *G = createNode('G');
	Node *H = createNode('H');
	Node *I = createNode('I');
	Node *J = createNode('J');
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	D->left = G;
	D->right = H;
	C->right = F;
	F->left = I;
	F->right = J;


	printf("전위 순회: ");
	preorder(A);
	printf("\n");

	printf("후위 순회: ");
	postorder(A);
	printf("\n");

	printf("중위 순회: ");
	inorder(A);
	printf("\n");

	return 0;
}