Data-Structures Binary Search Tree Q4 - Post Order Iterative 풀이

오늘 코드 리뷰 상대가 스택 하나를 사용해 후위 순회를 구현한 코드를 올려주셔서 열심히 해석해보았다.

덕분에 가장 어려웠던 문제를 이해할 수 있게 되었다 :D 

문제 해석 : 

post-order(후위 순회)로 트리의 노드를 읽으시오.

스택을 사용하시오

 

후위 순회란 :

후위 순회 방문 순서는 다음과 같다.

1. 왼쪽 서브트리

2. 오른쪽 서브트리

3. 자기 자신(root)

이미지 출처:https://dongsik93.github.io/algorithm/2019/09/29/algorithm-theory-binarytree/

 

손으로 그려보면 방문 순서를 도출해내는 건 쉽다. 하지만 코드로 구현하기가 어렵다.

재귀로 풀면 점화식만 도출하면 되므로 쉬운데 스택을 쓰라니..

 

 

구현 아이디어 떠올리기 :

후위 순회의 성질을 잘 생각해보면 이런 규칙이 있다.

💡 어떤 노드를 방문하기 위해서는 반드시 왼쪽 자식 노드, 오른쪽 자식 노드를 모두 방문해야 함

이 규칙을 활용하면 스택으로 풀 수 있다.

 

(아래 과정은 정확하지 않음,, 그림 참고 바람)

 

• 먼저 스택에 루트를 넣고
• 스택이 빌 때까지 다음을 실행한다. 
  • 왼쪽 자식 노드가 존재하면 계속 push 
  • 왼쪽 자식 노드가 더 이상 없으면 (NULL) 오른쪽 자식 노드가 있는지 확인
    • 오른쪽도 없으면 (NULL) 왼쪽 자식, 오른쪽 자식 모두 방문 완료한 것과 마찬가지로 취급됨.
      본인을 방문하기 위한 조건이 만족되었으므로 스택에서 pop, visit에 저장
      • * pop한 노드를 visit에 저장하는 이유는 마지막으로 방문한 노드가 오른쪽 자식인지 판단하기 위함이다.
        오른쪽 자식이면 그 부모 노드를 방문하기 위한 조건이 모두 만족된 것이므로 스택에서 바로 pop하면 됨
      • 방금 pop된 노드(visit)와 스택의 탑을 비교
        • visit이 스택의 탑의 오른쪽 노드이면 스택의 탑을 방문하기 위한 조건이 만족되었으므로 스택에서 pop, visit에 저장
        • visit이 스택의 탑의 왼쪽 노드이면 아직 오른쪽에 방문할 노드가 남아있을 수 있기 때문에 오른쪽 자식을 탐색
    • 오른쪽이 있으면 아직 오른쪽 방문 안 했다는 뜻이므로 본인을 방문하기 위한 조건이 만족되지 않았음.
      먼저 방문 완료되어야 할 오른쪽 자식을 스택에 push
    • 다시 while문의 처음으로 돌아가서 똑같이 진행

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

	Stack s;
	s.top = NULL;
	push(&s, root);
	int visit = root->item;
	while(!isEmpty(&s)){
		if(peek(&s)->right != NULL && peek(&s)->right->item == visit){ //오른쪽 노드를 방문했으면
			BSTNode* cur = pop(&s); //pop(방문)
			visit = cur->item;
			printf("%i ", cur->item);
			continue;
		}
		while(peek(&s)->left != NULL && peek(&s)->left->item != visit){ //스택에 왼쪽 노드 삽입
			push(&s, peek(&s)->left);
		}
		if(peek(&s)->right == NULL){ //오른쪽 노드가 없으면
			BSTNode* cur = pop(&s); //pop(방문)
			visit = cur->item;
			printf("%i ", cur->item);
		}
		else{ //오른쪽 노드가 있으면
			push(&s, peek(&s)->right); //오른쪽 노드를 삽입
		}
	}
}

 

 

 

https://www.youtube.com/watch?v=xLQKdq0Ffjg