[WEEK05] 스택을 사용한 BST 후위 순회 구현하기

💻 코드 구현

void postOrderIterativeS1(BSTNode *root)
{
	if (root == NULL) return;
	Stack stack;
	stack.top = NULL;

	BSTNode *cur;
	push(&stack, root);

	while(!isEmpty(&stack)) {
		cur = pop(&stack);
		if (cur->left == NULL && cur->right == NULL) printf("%d ", cur->item);
		else {
			BSTNode *tmp = malloc(sizeof(BSTNode));
			if (tmp != NULL) {
				tmp->item = cur->item;
				tmp->left = NULL;
				tmp->right = NULL;
				push(&stack, tmp);
			}
		}
		if (cur->right != NULL) push(&stack, cur->right);
		if (cur->left != NULL) push(&stack, cur->left);
	}

	return;
}

코드 실행 결과

🔎 코드 동작 과정

• 후위 순회로 출력을 해야 하기 때문에, 스택에 push할 때는 역순(루트→오른쪽 자식→왼쪽 자식) 순으로 진행했다.
• 루트를 그냥 스택에 push할 때 발생하는 무한 반복 문제를 해결하기 위해 자식이 연결되지 않은 tmp라는 노드를 루트 대신 스택에 push하였다.

🔥 트러블 슈팅

• 스택에 루트 노드를 push했더니 루트 노드에 연결된 왼쪽 자식과 오른쪽 자식이 계속해서 스택에 push되어서 무한 반복되는 문제가 발생했다.
• “어떻게 해야 무한 반복되는 현상을 해결할 수 있을까?”
  • BSTNode* tmp를 malloc으로 생성해서 root의 item 값만 복사하고 스택에 push하자!
  • 스택에서 tmp로 생성된 노드가 pop되어도 왼쪽 자식과 오른쪽 자식이 연결되어 있지 않기 때문에 무한으로 스택에 삽입되는 현상 방지

👨‍🔬 배운 점

• struct 구조체 개념 이해
• pointer 개념 이해
• 연결 리스트 구현 및 이해
• BST 구현 및 이해