Post-order Traveral

: 후위 순회 방법은 루트를 가장 나중에 방문하는 방법이다.
: 왼쪽 자식, 오른쪽 자식, 루트 순서로 방문한다.

이 과정을 Recursive로 구현하면 아주 간결하다.
왼쪽 자식을 방문하고, 오른쪽 자식을 방문하고, 마지막에 루트를 방문하는 것이다.

Recursive

void postOrderTraversal(BSTNode *root)
{
    if (root == NULL)
        return;

    postOrderTraversal(root->left);     // 왼쪽 자식
    postOrderTraversal(root->right);    // 오른쪽 자식
    printf("%d ", root->item);          // 루트
}

후위 순회는 Stack으로 구현했을 때 난이도가 급상승한다.
Stack으로 구현하려면 루트 노드에서 pop을 해야하는지, 왼쪽 혹은 오른쪽 자식을 방문해야하는지 알기 까다롭기 때문이다.

단계별로 살펴보자.

1. 우선 가장 왼쪽 노드까지 내려간다.
2. 가장 왼쪽 노드에서 방문한다.
3. 루트 노드로 올라와서 오른쪽 노드가 있는지 확인한다.
4. 오른쪽 노드가 있다면 방문한다.
5. 루트 노드로 올라온다.
   여기서, 오른쪽 노드를 재방문하면 안 되는 것이 key point이다. 마지막에 방문한 노드를 저장하고, 방문한 노드와 오른쪽 노드가 같다면 추가하지 않고 leaf 노드로 본다.
   방문하고 1번부터 반복한다.

이해가 어렵다. 그림으로 보자.
1. 루트 노드에서 가장 왼쪽 노드까지 내려간다.

2. leaf 노드는 방문하고 다시 root로 올라간다.
   

3. 오른쪽 노드가 존재하고 이미 방문하지 않았다. stack에 추가한다.
   

4. 18을 확인했더니 leaf 노드이다. 방문한다.
   

5. 15를 확인했더니 오른쪽 노드와 최근 방문한 노드(18)이 같다. 이미 방문했기 때문에 18을 추가하지 않고 더이상 방문할 자식 노드가 없기에 15를 방문한다.
   

6. 20을 확인했더니 왼쪽 노드는 이미 방문하였고, 방문하지 않은 오른쪽 노드가 있다. 오른쪽 노드(50)를 추가한다.
   

7. 50을 확인했더니 왼쪽 노드가 있다. 왼쪽 노드(25)를 추가한다.
   

8. 25를 확인했더니 leaf 노드이다. 방문한다.
   

9. 50을 확인했더니 왼쪽 노드는 이미 방문하였고, 방문하지 않은 오른쪽 노드가 있다. 추가한다.
   

10. 80을 확인했더니 leaf 노드로 방문한다.
    

11. 50을 확인했더니 좌, 우 이미 방문하였기 때문에 root인 50을 방문한다.
    

12. 위와 동일하게 마지막으로 20을 방문한다.
    

Stack

void postOrderIterativeS1(BSTNode *root)
{
	/* add your code here */
	Stack *stack = (Stack *)malloc(sizeof(Stack));
	stack->top = NULL;

	BSTNode *cur = root;
	BSTNode *lastVisit = NULL;

	while (!isEmpty(stack) || cur)
	{
		// 왼쪽 끝까지
		while (cur)
		{
			push(stack, cur);
			cur = cur->left;
		}

		cur = peek(stack);

		// 오른쪽 노드가 없거나 이미 방문했다면 cur pop
		if (cur->right == NULL || cur->right == lastVisit)
		{
			lastVisit = pop(stack);
			printf("%d ", lastVisit->item);
			cur = NULL; // 루트 노드 삭제 후에는 다시 peek해봐야 함
		}

		// 왼쪽 노드를 전부 방문한 상태에서 오른쪽 노드가 있다면 다시 탐색
		else
			cur = cur->right;
	}
}