[C++] 이진트리(binary tree) 전위 순회, 중위 순회, 후위 순회, 레벨 순서 순회

 안녕하십니까, 오늘은 이진트리의 전위 순회, 중위 순회, 후위 순회에 대한 글을 포스팅해보겠습니다. 제가 전자공학과라서 컴퓨터 쪽이 약하다 보니, 정보처리 기사 자격증을 획득해야겠다 다짐한 적이 있습니다. 현재, 바쁜 일이 많아서 필기만 통과한 상태인데 당시에 이진트리가 무엇인지도 모르고 이런 순회 방식들도 마구잡이로 외워서 시험만 쳤던 기억이 있습니다. 해당 내용에 대해서 사실 최근까지 정확히는 모르다가 혼자 책 읽고 공부하다 알게 되어 이에 대해서 포스팅해보겠습니다.

 

1. 이진트리

 이진트리는 노드를 이용한 자료구조입니다. 제가 이전에 노드와 이진트리를 사용해서 적응형 호프만 코딩을 구현한 게시물이 있습니다. 궁금하시면 확인해보시길 바라겠습니다.

[C++] Adaptive Huffman Coding(적응형 허프만 코딩) (tistory.com)

[C++] Adaptive Huffman Coding(적응형 허프만 코딩)

이진트리의 구조는 각 노드가 두 개까지의 자식 노드를 보유하는 트리형 구조입니다. 아래는 제가 적응형 허프만 코딩을 할 때 그렸던 그림인데, 보시는 것처럼 맨 위의 루트 노드로부터 최대 두 개씩의 자식 노드를 생성하며 트리 구조를 생성해 나가게 됩니다. 트리라는 이름에 맞게 마치 나무를 뒤집어 놓은 모습으로 생각하실 수 있습니다.

template <typename T>
struct node {
	T data;
	node<T>* left;
	node<T>* right;

};

각 노드의 구조는 이렇게 데이터와, 왼쪽 자식 노드 주소 오른쪽 자식 노드 주소로 이뤄져 있습니다. 이런 식으로 노드가 만들어져 있을 때 탐색 알고리즘 네 가지에 대해서 알아보겠습니다.

 

2. 전위 순회(preorder traversal)

전위 순회는 탐색 순서가 (부모 -> 왼쪽 자식 -> 오른쪽 자식)으로 이루어지게 됩니다

그림. 이진 트리 예시

즉, 이진트리 예시 그림으로 예를 들어 제가 3번 노드에서 해당 탐색법을 이용할 경우 3 -> 5 -> 6 순서로 탐색이 진행됩니다. 이걸 전체 트리에 적용시켜 루트에서부터 전위 탐색을 사용하게 되면 어떻게 될까요?

결과는 0, 1, 2, 3, 5, 6, 4, 7, 8 순서로 탐색이 일어나게 됩니다. 이에 대한 탐색 코드는 아래와 같습니다.

template <typename T>
void preorder_tracer(node<T>* run_point) {
	if (!run_point) return;

	cout << run_point->data << endl;
	preorder_tracer(run_point->left);
	preorder_tracer(run_point->right);
}

3. 중위 순회(in-order traversal)

 그렇다면 중위 순회는 어떨까요? 중위 탐색은 (왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드) 순서로 탐색이 이뤄집니다. 마찬가지의 예시로 노드 3에서 보면 5->3->6 순서로 이뤄지게 될 것으로 예상할 수 있습니다.

중위 탐색을 이용해 루트 노드에서 탐색을 하면 어떻게 될까요? 

결과는 5, 3, 6, 2, 7, 4, 8, 1, 0 순서가 됩니다. 왼쪽부터 착실히 탐색이 되네요.

이에 대한 코드는 아래와 같습니다.

template <typename T>
void inodrer_tracer(node<T>* run_point) {
	if (!run_point) return;
	inodrer_tracer(run_point->left);
	cout << run_point->data << endl;
	inodrer_tracer(run_point->right);
}

4. 후위 순회(post-order traversal)

 후위 순회는 자식 노드들부터 탐색하는 알고리즘으로 (왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드) 순으로 탐색을 진행하게 됩니다. 역시 3번 노드에서 이를 해석해보면 5, 6, 3 순서로 검색이 이뤄지겠군요

 루트 노드에서부터 전체 트리에서 검색을 하면 어떨까요?

결과는 5, 6, 3, 7, 8, 4, 2, 1, 0 순서로 이뤄지게 됩니다. 이에 대한 코드는 아래와 같습니다.

template <typename T>
void postodrer_tracer(node<T>* run_point) {
	if (!run_point) return;
	postodrer_tracer(run_point->left);
	postodrer_tracer(run_point->right);
	cout << run_point->data << endl;

}

5. 레벨 순서 순회(level oreder traversal)

 레벨 순서 순회는 루트 노드부터 아래 노드로 같은 높이(hegiht)의 노드를 왼쪽 노드에서부터 오른쪽 노드로 검색하는 방법입니다. 즉 전체 트리에서 탐색을 진행할 경우 결과는

0

1

2

3 4

5 6 7 8

과 같은 형태로 순회하게 됩니다.

이에 대한 코드는 아래와 같고, 저는 BFS를 이용해 이를 만들었습니다. 다음에 BFS에 대해서 제가 한번 글을 쓰도록 하겠습니다.

template<typename T>
void levelorder_tracer(node<T>* run_point) {
	if (!run_point) return;
	queue<node<T>*> Queue_;
	Queue_.push(run_point);
	while (!Queue_.empty()) {
		int tmp_size = Queue_.size();
		for (int i = 0; i < tmp_size; i++) {
			node<T>* current = Queue_.front();
			cout << current->data << " ";
			if (current->left != NULL) Queue_.push(current->left);
			if (current->right != NULL) Queue_.push(current->right);
			Queue_.pop();
		}
		cout << endl;
		
	}

 

네 이렇게 이진트리와 순회 방법들에 대해서 알아봤습니다. 저도 리마인드하고 좋았던 것 같습니다. 다음도 제가 공부한 내용 또는 제가 구현에 시도한 코딩 방법을 통해 찾아뵙도록 하겠습니다. 감사합니다.