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

Binary Search Tree (5) - postOrderIterativeS2 함수 구현하기

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

주어진 요소 확인하기

구조체

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

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

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

postOrderIterativeS2 함수의 매개 변수

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

 

핵심 아이디어

• 루트 노드가 NULL이면 바로 종료
• 출력용 스택 하나를 추가로 사용하여, 후위 순회를 마치 전위 순회처럼 쉽게 구현
  • 순회용 스택을 이용해 전위 순회처럼 탐색을 시작하며, 루트 노드를 push하고 시작
  • 순회용 스택이 남아있는 동안 반복되는 while문을 연다.
    • 노드를 하나 pop하여 출력용 스택에 push
    • 왼쪽 자식이 있다면 먼저 push (출력용 스택에서 오른쪽이 나중에 pop되도록)
    • 오른쪽 자식이 있다면 그 다음 push
• 이 과정을 통해 출력용 스택에는 자연스럽게 루트 → 오른쪽 → 왼쪽 순으로 저장됨
• 출력용 스택을 pop하면서 출력하면, 왼쪽 → 오른쪽 → 루트의 순서로 출력됨
  
  • 이는 문제에서 요구하는 후위 순회의 정의와 정확히 일치

 

구현하기

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

	// 순회용 스택, 출력용 스택 선언 및 초기화
	Stack stk, print_stk;
	stk.top = print_stk.top = NULL;

	// 루트 노드를 순회용 스택에 push
	push(&stk, root); 

	BSTNode *cur;
	while (!isEmpty(&stk)) {
		// stk에서 노드를 하나 꺼내 print_stk에 push
		cur = pop(&stk);
		push(&print_stk, cur);

		// 왼쪽 자식을 먼저 push (오른쪽 자식이 먼저 처리되게)
		if (cur->left) push(&stk, cur->left);
		// 이어서 오른쪽 자식을 push
		if (cur->right) push(&stk, cur->right);
	}

	// 순회 후 print_stk에는 루트->오른쪽->왼쪽 순으로 저장되어 있음
	// print_stk을 최상단부터 pop하면 왼쪽->오른쪽->루트 순으로 출력됨
	while (print_stk.top != NULL) {
		printf("%d ", pop(&print_stk)->item);
	}
}