스택 1개만으로 트리 순회하기

typedef struct _bstnode
{
	int item;
	struct _bstnode *left;
	struct _bstnode *right;
} BSTNode; // You should not change the definition of BSTNode

typedef struct _stackNode
{
	BSTNode *data;
	struct _stackNode *next;
} StackNode; // You should not change the definition of StackNode

typedef struct _stack
{
	StackNode *top;
} Stack; // You should not change the definition of Stack

기본적으로 주어지는 구조체

처음에는 재귀를 스택으로 구현해야 하는데, 중간 진행 상황을 어디에 저장해야 하나 고민했다. 재귀 함수의 경우 진행 상황이 기본적으로 본인의 스택 프레임 내에 저장되어 있기 때문에 돌아와도 어디부터 시작할 지 알고 있다.

학부 때 배운 순회에서는 스택 두개로 구현했었는데 한개로만 구현하려니 골치가 아팠다. 처음에는 오른쪽 서브트리를 방문했는지 확인하는 플래그, 그리고 내려가면서 확인하는 중인지 검사하는 플래그를 썼는데, 코드의 복잡도가 높아지고 이전 상황이 제대로 저장되지 않아서 결국 GPT의 힘을 빌렸다.

void postOrderIterativeS1(BSTNode *root)
{

	Stack stack;
	stack.top = NULL;

	BSTNode *cur = root;
	BSTNode *lastVisited = NULL;

	while (!isEmpty(&stack) || cur)
	{
		if (cur)
		{
			push(&stack, cur);
			cur = cur->left;
		}
		else
		{
			BSTNode *parent = peek(&stack);

			if (parent->right && lastVisited != parent->right)
			{
				cur = parent->right;
			}
			else
			{
				printf("%d\\n", parent->item);
				lastVisited = pop(&stack);
			}
		}
	}
}

참고로 함수 내에서만 사용되는 구조체의 경우 동적할당을 하는 것보다는 정적 선언으로 함수가 종료될때 자연스럽게 같이 없어지도록 하는 편이 코드의 복잡도 (예를 들면 free를 해주는 것) 측면에서 훨씬 편하긴 하다.

코드의 진행 과정을 아래에 써놓도록 하겠다.

코드 진행 과정

1. root에 먼저 커서를 둔다.
2. 왼쪽 서브트리들을 먼저 전부 스택에 넣는다.
3. 커서가 null이라면, 부모 트리의 왼쪽 노드가 null이라는 소리이니 스택에 들어간 부모 노드의 오른쪽을 검사하고. 이전에 방문한 노드가 아니라면 커서를 오른쪽 노드로 옮긴다.
   1. 만약 이전에 검사한 노드이거나 오른쪽 노드가 없다면 peek은 리프 노드이므로 출력하고, 이 노드를 방문하여 출력했다는 의미로 lastVisited에 넣어준다.

제대로 동작하는 이유

BST 코드들을 작성할때, 스택에 이전 노드들을 저장해두고 현재 노드가 리프 노드라면 이전 노드들을 스택에서 꺼내어서 검사하는 과정에서 무한루프가 발생했었다. 나는 이 무한루프를 끊기 위해 자식 노드들과의 연결을 끊어버리는 방식을 사용했었는데, 이러면 트리의 구조가 바뀌어버려서 순회를 단 한번밖에 할 수 없었다. 이 코드에서는 미리 왼쪽을 모두 검사하고, 스택 내의 노드들은 오로지 오른쪽만 검사하도록 해 두어서 무한루프를 방지할 수 있었다. 커서가 존재할때, NULL 일 때 두 영역으로 나누어 버려서 이런 효과가 나타난 것이 아닌가 추측한다.