이진 트리와 순회 방식

이진 트리는 가장 많이 사용되는 비선형 자료구조다. 이진 트리를 사용하는 목적은 데이터의 탐색 속도의 증진을 위해 사용하는 것이다. 트리를 구현할 때는 배열이 아닌 포인터를 사용한다.

 

▷왜 포인터를 사용할까?

▶힙 정렬을 구현할 때는 완전 이진 트리 형식이기에 배열로 표현할 수 있었으나, 완전 이진 트리가 아닌 이진 트리는 배열로 구현하기 힘들기에 포인터를 사용하여 왼쪽 자식과 오른쪽 자식을 나타낸다!

 

 

이진 트리

1. 전위 순회(Preorder traversal)

   1) 자기 자신을 처리한다.

   2) 왼쪽 자식을 방문한다.

   3) 오른쪽 자식을 방문한다.

 

2. 중위 순회(Inorder traversal)

   1) 왼쪽 자식을 방문한다.

   2) 자기 자신을 처리한다.

   3) 오른쪽 자식을 방문한다.

 

3. 후위 순회(Postorder traversal)

   1) 왼쪽 자식을 방문한다.

   2) 오른쪽 자식을 방문한다.

   3) 자기 자신을 처리한다.

 

 

이진 트리

 

예를 들어 위와 같은 이진 트리를 각 순회 방법으로 탐색한다고 하면

 

▷전위 순회 : 1 - 2 - 4 - 8 - 9 - 5 - 10 - 11 - 3 - 6 - 12 - 13 - 7 - 14 - 15

 

▷중위 순회 : 8 - 4 - 9 - 2 - 10 - 5 - 11 - 12 - 6 - 13 - 3 - 14 - 7 - 15

 

▷후위 순회 : 8 - 9 - 4 - 10 - 11 - 5 - 2 - 12 - 13 - 6 - 14 - 15 - 7 - 3 - 1

 

과 같이 순회를 하게 된다.

 

 

#include <iostream>

using namespace std;

int num = 15;

typedef struct node *treePtr;
typedef struct node{
	int data;
	treePtr left, right;
}node;

void preorder(treePtr ptr) {
	if (ptr) {
		printf("%d ", ptr->data);
		preorder(ptr->left);
		preorder(ptr->right);
	}
}

void inorder(treePtr ptr) {
	if (ptr) {
		inorder(ptr->left);
		printf("%d ", ptr->data);
		inorder(ptr->right);
	}
}

void postorder(treePtr ptr) {
	if (ptr) {
		postorder(ptr->left);
		postorder(ptr->right);
		printf("%d ", ptr->data);
	}
}

int main() {
	node nodes[16];

	for (int i = 1; i < 16; i++) {
		nodes[i].data = i;
		nodes[i].left = NULL;
		nodes[i].right = NULL;
	}

	for (int i = 1; i < 16; i++) {
		if (i % 2 == 0) {
			nodes[i / 2].left = &nodes[i];
		}
		else {
			nodes[i / 2].right = &nodes[i];
		}
	}

	preorder(&nodes[1]);
	printf("\n");
	inorder(&nodes[1]);
	printf("\n");
	postorder(&nodes[1]);
	
}