이진트리의 구현과 순회 방식

이진 트리는 데이터의 탐색 속도 증진을 위해 사용하는 구조이다.

 

완전 이진 트리가 아닌 이진 트리는 배열로 표현하기 어렵기 때문에 포인터(Pointer)를 사용하는데,

 

포인터를 통해 특정한 Root에서 자식 노드로 접근할 수 있다.

 

이진트리 데이터 탐색 순회 방식은 전위순회, 중위순회, 후위순회 총 3가지가 존재한다.

 

1. 전위순회 (Preorder Traversal)

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

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

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

 

2. 중위순회 (Inorder Traversal)

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

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

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

 

3. 후위순회 (Postorder Traversal)

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

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

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

이진 트리 (Binary Tree)

 

즉, 다음과 같은 이진트리가 존재할 때, 각각의 순회 방문 순서는 

 

전위순회 (Preorder Traversal) :  1  2  4  8  9  5  10  11  3  6  12  13  7  14  15

 

중위순회 (Inorder Traversal) :  8  4  9  2  10  5  11  1  12  6  13  3  14  7  15

 

후위순회 (Postorder Traversal) :  8  9  4  10  11  5  2  12  13  6  14  15  7  3  1      이다. 

 

[예제]

#include <iostream>

using namespace std;

int number = 15;

typedef struct node *treePointer;
typedef struct node {
	int data;
	treePointer leftChild, rightChild;
} node;

//전위 순회
void preorder(treePointer ptr) {
	if(ptr) {
		cout << ptr -> data << ' ';
		preorder(ptr -> leftChild);
		preorder(ptr -> rightChild);
	}
} 

//중위 순회
void inorder(treePointer ptr) {
	if(ptr) {
		inorder(ptr -> leftChild);
		cout << ptr -> data << ' ';
		inorder(ptr -> rightChild);
	}
} 

//후위 순회
void postorder(treePointer ptr) {
	if(ptr) {
		postorder(ptr -> leftChild);
		postorder(ptr -> rightChild);
		cout << ptr -> data << ' ';
	}
} 

int main() {
	node nodes[number + 1] ;
	for(int i=1; i<=number; i++) {
		nodes[i].data = i;
		nodes[i].leftChild = NULL;
		nodes[i].rightChild = NULL;
	}
	for(int i=1; i<=number; i++) {
		if(i%2 == 0) {
			nodes[i/2].leftChild = &nodes[i];
		} else {
			nodes[i/2].rightChild = &nodes[i];
		}
	}
	preorder(&nodes[1]);
	cout << endl;
	inorder(&nodes[1]);
	cout << endl;
	postorder(&nodes[1]);
}

 

해당 소스코드는 C++로 작성한 코드이다.

 

노드의 개수는 15개로 정의해준 뒤, 구조체를 사용하여 하나의 노드 정보를 선언하기 위한 포인터를 정의해준다.

 

즉, node라는 구조체를 treePointer라는 이름의 포인터 형식으로 사용하도록 한다.

 

node 구조체를 정의할 때 왼쪽 노드를 가리키는 포인터변수와 오른쪽 노드를 가리키는 포인터변수를 생성한다.

 

각 순회 방식에서는 순서만 바꾸면 되는데, 전위 순회는 해당 포인터가 NULL 값이 아니라면 자기 자신을 먼저 출력하여

 

처리하고 왼쪽 노드를 기준으로 하여 전위 순회를 수행해준 뒤, 오른쪽 노드를 기준으로 하여 전위 순회를 수행해준다.

 

중위 순회는 해당 포인터가 NULL 값이 아니라면 왼쪽 노드를 기준으로 하여 중위 순회를 수행하고 자기 자신을 출력하여

 

처리한다. 그 후, 오른쪽 노드를 기준으로 하여 중위 순회를 재귀적으로 수행해준다.

 

마찬가지로 후위 순회 또한, 해당 포인터가 NULL 값이 아니라면 왼쪽 노드를 기준으로 하여 후위 순회를 수행하고

 

오른쪽 노드를 기준으로 하여 후위 순회를 수행한 다음, 자기 자신을 출력하여 처리한다.

 

메인코드에서는 총 15개의 node가 담길 수 있는 데이터 배열을 생성하고 왼쪽 자식 노드와 오른쪽 자식 노드를

 

NULL 값으로 초기화 시켜주도록 한다. 

 

각 노드를 연결시켜주기 위해 변수 i가 2의 배수라면 2로 나눈 값의 왼쪽 자식 노드를 자기 자신으로 설정하고

 

홀수라면 2로 나눈 값의 오른쪽 자식 노드를 자기 자신으로 설정한다. 최종적으로 각 순회 방식을 진행한다.

 

[결과]

이진트리의 구현과 순회 방식 결과

 

---

출처

https://blog.naver.com/ndb796/221233560789

19. 이진 트리의 구현과 순회(Traversal) 방식