트리 - 반복적 순회(전위/중위/후위 순회 스택으로 이해하기)

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다.

 

이전 글: 트리-이진트리 순회

 

반복적 순회

스택 stack 자료구조와 for문을 이용해 트리를 순회하는 방식이다.

 

이전까지는 순환 호출을 이용해 순회를 했다면 반복적 순회는 for문과 스택을 이용한다.

 

전위/중위/후위 순회 모두 반복적 순회를 이용해 구현할 수 있다.

이전 글에서 예시로 들었던 아래의 트리를 이용해 전위/중위/후위 반복적 순회를 모두 살펴보자.

---

스택 그림만으로 방문 순서 알아내기

*pseudo-code: 프로그래밍 언어는 아니지만 유사한 모양으로 알고리즘의 원리를 설명할때 사용가능

1. 전위 순회

// Pseudo Code
preorder_iter(node):
	if(node == NULL)
		return
	s <- empty stack
	s.push(node)
	while (not s.isEmpty())
		node <- s.pop()
		visit(node)
		if(node.right != NULL)
			s.push(node.right)
		if(node.left != NULL)
			s.push(node.left)

  위의 pseudo code을 이해해보면, 전위순회의 정의에 의거, 루트 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 방문하기 때문에 스택에는 오른쪽 서브트리가 먼저 push되고, 왼쪽 서브트리가 push된다. 그 다음에는 pop하여 그 노드를 방문하고 그 노드의 오른쪽 서브트리, 왼쪽 서브트리를 push하는 과정을 반복한다.

 

  모니터링 코드(stack_status)를 추가하여 실행한 결과는 다음과 같다.

루트 노드 A를 방문한 뒤, A의 오른쪽 서브트리의 루트노드 C를 먼저 push 하고, 왼쪽 서브트리의 루트노드 B를 push했다. 그 다음에는 pop하여 B 노드를 방문한 뒤, B의 오른쪽, 왼쪽 서브트리를 순서대로 push한다. 

이 과정을 스택이 공백이 될 때까지 반복하면 된다.

2. 중위 순회

// Pseudo Code
inorder_iter(node):
	s <- empty stack
	while (not s.isEmpty() OR node != NULL)
		if (node != NULL)
			s.push(node)
			node <- node.left
		else
			node <- s.pop()
			visit(node)
			node <- node.right

  위의 Pseudo-Code를 살펴보면, 중위순회의 정의에 의거, 왼쪽 서브트리->루트노드->오른쪽 서브트리 순으로 방문하기 때문에 스택에는 왼쪽 서브트리가 우선적으로 push된다. 만약 왼쪽 서브트리가 NULL 이라면, pop하고 그 노드의 오른쪽 서브트리를 새로운 노드로 지정한다. 만약 오른쪽 서브트리도 NULL이라면, 또 pop 하는 방식이다. 

 

  중위순회는 전위순회보다 조금 더 이해하기 복잡하다. 쉽게 생각하면 다음과 같이 정리할 수 있다.

현재 노드가 NULL이 아니면, push하고 현재노드의 왼쪽 서브트리의 루트노드를 새로운 노드로 지정한다.
현재 노드가 NULL이면, pop하고 현재 노드의 오른쪽 서브트리의 루트노드를 새로운 노드로 지정한다.

 

  모니터링 코드(stack_status)를 추가하여 실행한 결과는 다음과 같다.

현재 노드가 NULL이 아닐때까지, 왼쪽 서브트리의 루트노드를 새로운 노드로 지정하는 과정을 반복하며 stack에 push한다. A->B->D순으로 push 하다가, 노드 D는 단말노드로 왼쪽 서브트리가 NULL이므로 pop하고 방문한다. 그 뒤에는 D의 오른쪽 서브트리를 새로운 노드로 지정하지만, NULL 이므로 또 pop하여 노드 B를 방문한다.  노드 B의 오른쪽 서브트리는 E 이므로 push하고 E의 왼쪽 서브트리를 새로운 노드로 지정한다. 이 노드는 NULL 이므로 pop하면 E를 방문하게 되고, E의 오른쪽 서브트리를 새로운 노드로 지정한다. 노드 E는 단말노드이기 때문에 또 NULL 이므로 pop하여 A를 방문한다. 이 과정을 새롭게 지정된 노드가 NULL 이거나 스택이 공백 상태가 될때까지 반복한다. 

3. 후위 순회

postorder_iter(node):
	s <- empty stack
	t <- output stack // 방문순서를 저장할 배열
	s.push(node)
	while(not s.isEmpty)
		node <- s.pop()
		t.push(node)
		if(node.left != NULL)
			s.push(node.left)
		if(node.right != NULL)
			s.push(node.right)
	while(not t.isEmpty)
		node <- t.pop()
		visit(node)

위의 Pseudo-Code를 살펴보면, 후위순회 정의에 의거 왼쪽 서브트리->오른쪽 서브트리 -> 루트 노드 순으로 방문하기 때문에 스택에 루트 노드를 push 한다. 이 아래의 과정은 스택이 공백 상태가 아닐때까지 반복하면 된다.

우선 pop하고, pop한 노드를 출력 배열에 저장한 뒤, 이 노드의 왼쪽 서브트리의 루트노드, 오른쪽 서브트리의 루트노드를 순서대로 push한다. 

스택이 공백상태가 되면, 출력 배열에 저장한 원소들을 역순으로 출력하면 후위순회 순서를 알 수 있다.

 

모니터링 코드(stack_status)를 추가하여 실행한 결과는 다음과 같다.

루트 노드 A가 push되고, A가 pop된 뒤에, 

A의 왼쪽 서브트리의 루트노드 B, 오른쪽 서브트리의 루트 노드 C가 순서대로 push된다.

노드 C가 pop된 뒤에, C의 왼쪽 서브트리의 루트노드인 F를 push한다.

이 과정은 스택이 공백상태가 될 때까지 반복된다.

---

c언어로 구현

#include <stdio.h>
#include <stdlib.h>

#define SIZE 20
typedef struct TreeNode {
	char data;
	struct TreeNode* left, * right;
} TreeNode;

int top = -1;
TreeNode* stack[SIZE];

//				A	
//		B				C
// 	 D	   E		F

// 스택에 노드 추가
void push(TreeNode* p)
{
	if (top < SIZE - 1) {
		stack[++(top)] = p;
	}
}
// 스택에서 노드 꺼내기
TreeNode* pop() {
	TreeNode* p = NULL;
	if (top >= 0) {
		p = stack[top--];
	}
	return p;
}
// 스택의 현 상태 출력
void stack_status() {
	printf("\tStack_status: [");
	for (int i = top; i >= 0; i--)
	{
		printf("%c, ", stack[i]->data);
	}
	printf("]\n");
}

// 반복적 전위 순회
void preorder_iter(TreeNode* root) 
{
	push(root);
	while (top >= 0)
	{
		TreeNode* current = stack[top];
		TreeNode* del = pop();
		printf("Visited: %c  ", del->data);
		printf("\n");
		TreeNode* temp = current->right;
		if (temp != NULL) {
			push(temp);
		}
		temp = current->left;
		if (temp != NULL) {
			push(temp);
		}
		stack_status();
	}
}
// 반복적 중위 순회
void inorder_iter(TreeNode* root)
{
	top = -1;
	TreeNode* current = root;
	
	// 스택으로 표현했을 때 좀 더 직관적인 코드
	while (top >= 0 || current != NULL)
	{
		if (current != NULL) {
			push(current);
			current = current->left;
		}
		else {
			current = pop();
			printf("Visited: %c ", current->data); printf("\n");
			current = current->right;
		}
		stack_status();
	}
	
	/*
	// 순회의 의미를 더 잘 담고 있는 코드
	while (1) {
		while (current != NULL) {
			push(current);
			current = current->left;
		}
		current = pop();
		if (current == NULL) {
			break;
		}
		else {
			printf("Visited: %c ", current->data);
			current = current->right;
		}
		printf("current = %c\n", current->data);
		stack_status();
	}
	*/
}
// 반복적 후위 순회
void postorder_iter(TreeNode* root)
{
	top = -1;
	int i = 0;
	TreeNode* node;
	TreeNode* output[SIZE];
	push(root);
	while (top >= 0) {
		node = pop();
		output[i++] = node;
		if (node->left != NULL)
			push(node->left);
		if (node->right != NULL)
			push(node->right);
		stack_status();
	}
	printf("Visited: ");
	for (i = i-1; i >= 0; i--)
		printf("%c -> ", output[i]->data);
	
}

TreeNode n0 = { 'D', NULL, NULL };
TreeNode n1 = { 'E', NULL, NULL };
TreeNode n2 = { 'B', &n0, &n1 };
TreeNode n3 = { 'F', NULL, NULL };
TreeNode n4 = { 'C', &n3, NULL };
TreeNode n5 = { 'A', &n2, &n4 };
TreeNode* root = &n5;

int main()
{
	printf("*********전위 순회*********\n\n");
	preorder_iter(root);
	printf("\n\n*********중위 순회*********\n\n");
	inorder_iter(root);
	printf("\n\n*********후위 순회*********\n\n");
	postorder_iter(root);
	printf("\n");
	return  0;
}