[C언어] Binary Search Tree (4) - postOrderIterativeS1 함수 구현하기

Binary Search Tree (4) - postOrderIterativeS1 함수 구현하기

이진 탐색 트리의 후위 순회에 대해 스택 1개를 사용하여 반복문으로 구현하고, 순회 결과를 출력하는 함수

주어진 요소 확인하기

구조체

• BSTNode: (struct) 이진 탐색 트리 노드 구조체
  • item: (int field) 노드의 값
  • *left: (pointer field) 왼쪽 자식 노드 주소
  • *right: (pointer field) 오른쪽 자식 노드 주소

• StackNode: (struct) 스택 노드 구조체
  • *data: (pointer field) 이진 탐색 트리 노드 주소
  • *next: (pointer field) 다음(스택 아래쪽) 노드 주소

• Stack: (struct) 스택 구조체
  • *top: (pointer field) 스택 최상단 노드 주소

postOrderIterativeS1 함수의 매개 변수

• *root: (pointer) 이진 탐색 트리 루트 노드 주소

 

핵심 아이디어

• 루트 노드가 NULL이면 바로 종료
• 현재 노드를 추적할 포인터 cur, 마지막으로 방문한 노드를 추적할 포인터 last를 선언
• cur가 존재하거나 스택이 비어있지 않은 동안 반복되는 while문을 연다.
  • cur가 NULL이 아닐 동안 현재 노드를 스택에 push하고, 왼쪽 자식으로 이동
  • 왼쪽 자식이 더 이상 없으면 peek을 통해 스택 최상단 노드를 확인
  • 오른쪽 자식이 없거나, 이미 방문한 노드인 경우 해당 노드를 출력하고 pop
    • 이때 last를 현재 노드로 설정해 이미 방문한 오른쪽 서브트리 재진입을 방지
    • 추가로 cur를 NULL로 설정해 왼쪽 서브트리 재진입을 방지
  • 그렇지 않으면 오른쪽 자식으로 이동해 오른쪽 서브트리 순회 시작
• 위 과정을 반복한다.

 

구현하기

// 이진 탐색 트리의 후위 순회에 대해 스택 1개를 사용하여 반복문으로 구현하고, 순회 결과를 출력하는 함수
// 순서: 왼쪽 자식 → 오른쪽 자식 → 현재 노드
void postOrderIterativeS1(BSTNode *root) {
	// 루트 노드가 NULL인 경우 return
	if (root == NULL) return;

	// 임시 스택 선언 및 초기화
	Stack stk;
	stk.top = NULL;

	BSTNode *cur = root;     // 현재 탐색 중인 노드
	BSTNode *last = NULL;    // 마지막으로 방문한 노드 (오른쪽 자식 처리 여부 확인용)

	while (cur != NULL || !isEmpty(&stk)) {
		// 왼쪽 자식 끝까지 스택에 push
		while (cur != NULL) {
			push(&stk, cur);
			cur = cur->left;
		}

		// 스택 top을 꺼내지 않고 확인
		cur = peek(&stk);

		// 오른쪽 자식이 없거나, 이미 방문한 경우 -> 현재 노드를 방문
		if (cur->right == NULL || cur->right == last) {
			printf("%d ", cur->item);  // 현재 노드 출력
			pop(&stk);                 // 스택에서 제거
			last = cur;                // 마지막 방문 노드 갱신
			cur = NULL;                // 다시 왼쪽으로 내려가지 않게 설정
		} else {
			// 오른쪽 자식이 아직 방문되지 않았다면 오른쪽으로 이동
			cur = cur->right;
		}
	}
}