5주 차 - 이진 탐색 트리 - 재귀 없이 후위 순회 근데 이제 스택 두 개를 곁들인

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

데이터 분석

대상자

• 대상자_정보: 알고리즘/자료구조를 공부하는 중급 이상 개발자
• 난이도: 중급 (재귀 없이 스택을 사용한 트리 순회 구현 이해 필요)

핵심 요약

• 후위 순회(Post-order Traversal)는 Left → Right → Root 순서로 노드를 방문하는 트리 순회 방식
• 두 스택(S1, S2)을 사용해 재귀 없이 후위 순회를 구현: S1에 전위 순회 방식으로 노드를 저장, S2에 역순으로 저장
• 코드 구현 예시

```cpp

void postOrderIterativeS2(BSTNode *root) {

Stack s1, s2;

push(&s1, root);

while (!isEmpty(&s1)) {

current = pop(&s1);

push(&s2, current);

if (current->left != NULL) push(&s1, current->left);

if (current->right != NULL) push(&s1, current->right);

}

while (!isEmpty(&s2)) printf("%d ", pop(&s2)->item);

}

```

섹션별 세부 요약

1. 후위 순회 개념

• 후위 순회 정의: 왼쪽 자식 → 오른쪽 자식 → 루트 순서로 노드를 방문
• 예시 트리:

```

/ \

1. 15

```

• 결과: 5 15 10

2. 두 스택 활용 방식

• S1 스택 역할:

- 루트 → 왼쪽 → 오른쪽 순서로 노드를 push

- S2로 노드를 pop 후 저장

• S2 스택 역할:

- S1에서 pop한 노드를 역순으로 push → 최종 후위 순회 순서 생성

• 스택 구조:

- S1: 10 → 5 → 15

- S2: 15 → 5 → 10

3. 구현 코드 분석

• push 및 pop 함수:

- push(&s1, root)로 S1에 루트 노드 삽입

- pop(&s1)로 S1에서 노드를 추출 후 S2에 삽입

• 순회 로직:

- S1이 비워질 때까지 반복: S1에서 pop → S2에 push

- S2에서 pop하며 결과 출력

결론

• 두 스택 기반 후위 순회는 재귀 없이 트리 순회를 구현할 수 있는 효과적인 방법
• 핵심 팁: S1은 전위 순회 방식으로, S2는 역순 저장을 통해 후위 순회 결과를 생성
• 구현 시 주의사항: S1에 노드를 삽입할 때 left → right 순서로 push해야 함