[정글 week05] C언어 BST 후위 순회

Woody Jo·2025년 6월 18일

kjungle

목록 보기

12/31

C언어 주차에 들어섰다.

1. LinkedList
2. Stack and Queue
3. Binary Tree
4. Binary Search Tree

이렇게 문제를 풀어야 했다.

여기서는 4번 BST를 얘기할 예정이다.

무한 루프의 반복의 반복의 반복의 반복

15번을 건너뛰고 18번을 접근하려고 하니까 자꾸 무한 반복을 하게 됨…..

무한 루프에서 빠져나오지 못하는 늪에 빠졌다.
어떻게 해결 할 수 있을까.......

루트를 기준으로 왼쪽, 오른쪽 node들이 모두 존재할 때 출력하면 어떨까?

if (cur->left != NULL && cur->right != NULL) {
	printf("%d %d %d", cur->left->item, cur->right->item, cur->item);
}

위 코드의 예상 문제 케이스

중복이 발생하지 않을까? (왜냐하면 한 번에 left, right, root를 출력하려고 시도하였을 때)
- 중복 발생 가능성이 있어 root를 제외하면 출력될거 같은데?라는 착각
  - 그래서 root를 제외하고 과감한 시도

어 잘되는데??
어 아닌데?

정답 케이스

10 -> 18 -> 15 -> 25 -> 80 -> 50

완전 틀렸네?

조건을 다르게 하여 다시 도전!
왼쪽 자식의 오른쪽이 없을 때,
15의 오른쪽 자식이 있을 때 pushpush~

어? 루트 노드만 처리하면 되겠는걸?
번뜩!

while(cur != NULL || !isEmpty(s)) {

		// 왼쪽 서브 트리 순회
		while (cur != NULL) {
			push(s, cur);
			cur = cur->left;
		}
		
		if (s->top->data != root) {
			printf("%d ", s->top->data->item);
		};

		cur = pop(s);
		
		...
		...
		...
}
printf("%d ", root->item);
free(s);

마지막에 root→item을 추가할 수 있도록 처리

pdf에 예시처럼 정확하게 출력

끝난 줄 알았지?

테스트 케이스

오른쪽 서브 트리의 자식들이 있을 때 제대로 처리가 안된다………

여러 생각들을 하나씩 넣다 보니...?
그래서 좀 더 복잡해진 나의 코드(~~the love~~)

실패본 중 하나

while(cur != NULL || !isEmpty(s)) {

	// 왼쪽 서브 트리 순회
	while (cur != NULL) {
		push(s, cur);
		cur = cur->left;
	}
	// 이미 처리된 형제 노드가 현재 top일 때 pop
	if (s->top->data == tmp) {
		pop(s);
		continue;
	}
	cur = pop(s);
	// 현재 노드 root가 아닐 때만 출력
	if (cur != root) {
		printf("%d ", cur->item);
	}
	cur = cur->right;
	// 현재의 오른쪽이 이미 방문했던 노드라면?
	// s->top null 체크
	if (cur != NULL && cur->right == tmp && s->top != NULL) {
		cur = s->top->data->right;
		continue;
	}
	// 현재 노드의 오른쪽이 NULL이고, 
	// root의 오른쪽 형제 노드가 NULL이 아닐 때
	if (cur == NULL && s->top->data->right != NULL) {
		push(s, s->top->data->right);
		tmp = s->top->data;
		cur = tmp;
		// 오른쪽의 서브 트리의 root가 먼저 출력되는걸 방지
		if (tmp->left == NULL && tmp->right == NULL)
			printf("%d ", tmp->item);
	}
}
printf("%d ", root->item);

free(tmp);
free(s);

이것도 실패....

왜냐하면

18

25, 80, 50

중복된다….

최종본

void postOrderIterativeS1(BSTNode *root)
{
	 /* add your code here */
	if (root == NULL) return;

	Stack *s1 = malloc(sizeof(Stack));
	Stack *s2 = malloc(sizeof(Stack));
	BSTNode *cur = root;

	// BSTNode
	while(cur != NULL || !isEmpty(s1)) {
		// 오른쪽 서브 트리 순회로 스택에 쌓는다.
		while (cur != NULL) {
			push(s1, cur);
			push(s2, cur);
			cur = cur->right;
		}
		cur = pop(s1);
		cur = cur->left;
	}

	while(s2->top != NULL) {
		BSTNode *popItem = pop(s2);
		printf("%d ", popItem->item);
	}

	free(s1);
	free(s2);
}