개발하는데 다 이유가 있겠지

1. 큐를 이용해 순차적으로 탐색(BFS 방식?)

• 조건을 3가지로 구분해서 구현
  
  1. 자식 노드가 없는 경우
  2. 왼쪽 자식 노드만 있는 경우
  3. 오른쪽 자식 노드만 있는 경우

void levelOrderTraversal(BSTNode *root)
{
	Queue *q = malloc(sizeof(Queue));
	BSTNode *cur;
	
	q->head = NULL;
	q->tail = NULL;
	
	enqueue(&(q->head), &(q->tail), root);

	while (!isEmpty(q->head))
	{
		cur = dequeue(&(q->head), &(q->tail));
		printf("%d ", cur->item);
		if (cur->left == NULL && cur->right != NULL)
		{
			enqueue(&(q->head), &(q->tail), cur->right);
		}
		else if (cur->right == NULL && cur->left != NULL)
		{
			enqueue(&(q->head), &(q->tail), cur->left);
		}
		else if (cur->right == NULL && cur->left == NULL)
		{
			continue;
		}
		else
		{
			enqueue(&(q->head), &(q->tail), cur->left);
			enqueue(&(q->head), &(q->tail), cur->right);
		}
	}
}

---

2. 스택을 이용한 중위순회 구현하기

• 오른쪽 자식이 있는 경우와 오른쪽 서브 트리에서 왼쪽 자식 노드가 있는 경우를 고려함

void inOrderTraversal(BSTNode *root)
{
	// 스택을 할당하고 초기화
	Stack *s = malloc(sizeof(Stack));
	if (root == NULL)
	{
		// 루트가 NULL인 경우 처리하지 않고 함수 종료
		return;
	}

	// 왼쪽 자식 노드를 스택에 모두 추가
	while (root != NULL)
	{
		push(s, root);
		root = root->left;
	}

	// 스택이 비어있을 때까지 반복
	while (isEmpty(s) != 1)
	{
		// 스택에서 노드를 꺼내어 출력하고 오른쪽 자식으로 이동
		root = pop(s);
		printf("%d ", root->item);
		if (root->right != NULL)
		{
			// 오른쪽 자식이 있는 경우 해당 자식을 스택에 추가하고, 왼쪽 자식으로 이동하여 모든 왼쪽 자식을 스택에 추가
			root = root->right;
			push(s, root);
			if (root->right != NULL)
			{
				root = root->left;
				push(s, root);
			}
		}
		else
		{
			// 오른쪽 자식이 없는 경우 스택 처리를 계속 진행
			continue;
		}
	}

	// 메모리 해제
	free(s);
}

---

3. 스택을 이용한 전위순회 구현하기

• 스택이 빌 때까지 반복하면서 전위순회를 수행

void preOrderIterative(BSTNode *root)
{
	Stack *s = malloc(sizeof(Stack));

	push(s, root);
	if (root == NULL)
	{
		return;
	}

	while (isEmpty(s) != 1)
	{
		root = pop(s);
		printf("%d ", root->item);
		if (root->left != NULL && root->right != NULL)
		{
			push(s, root->right);
			push(s, root->left);
		}
		else if (root->left != NULL && root->right == NULL)
		{
			push(s, root->left);
		}
		else
		{
			continue;
		}
	}
}

---

4. 스택을 이용한 후위순회 구현하기

• peek() : 스택에서 제일 위에 위치한 노드를 반환
• last_visited 통해 가장 마지막에 방문한 노드를 갱신
• 스택의 맨 위 노드를 확인해서 오른쪽 자식이 비었거나, 오른쪽 자식에 방문했는지 여부를 확인

void postOrderIterativeS1(BSTNode *root)
{
	if (root == NULL) // 루트가 NULL이면 함수 종료
		return;

	Stack *s = malloc(sizeof(Stack)); // 스택을 할당하여 생성
	BSTNode *last_visited = NULL;	  // 마지막으로 방문한 노드를 나타내는 포인터 초기화

	while (1) // 무한 루프 시작
	{
		while (root != NULL) // 현재 노드가 NULL이 아닐 때까지 반복
		{
			push(s, root);	   // 현재 노드를 스택에 푸시
			root = root->left; // 왼쪽 자식 노드로 이동
		}

		if (isEmpty(s)) // 스택이 비어있으면 무한 루프 종료
			break;

		root = peek(s); // 스택의 맨 위 노드를 확인

		// 오른쪽 자식이 비어있거나 오른쪽 자식을 이미 방문했을 경우
		if (root->right == NULL || root->right == last_visited)
		{
			printf("%d ", root->item); // 현재 노드의 값을 출력 (후위 순회)
			pop(s);			// 스택에서 현재 노드를 팝
			last_visited = root;	   // 마지막으로 방문한 노드를 현재 노드로 설정
			root = NULL;			 // 현재 노드를 NULL로 설정하여 다음 반복에서 스택에서 팝하도록 함
		}
		else // 오른쪽 자식이 아직 방문되지 않았을 경우
		{
			root = root->right; // 오른쪽 자식 노드로 이동하여 다음 반복에서 처리
		}
	}

	free(s); // 스택에 할당된 메모리 해제
}

---

5. 스택을 두 개 사용해서 후위순회 구현하기

• s1 스택에는 자식 노드를 push
• s2 스택에는 s1 스택에서 pop한 노드들을 저장(기본으로 루트 노드를 push)
• 최종적으로 s2 스택에서 pop한 노드들을 출력하면 순서대로 순회 성공

void postOrderIterativeS2(BSTNode *root)
{
	Stack *s1 = malloc(sizeof(Stack));
	Stack *s2 = malloc(sizeof(Stack));
	if (root == NULL)
	{
		return;
	}
	push(s1, root);

	while (!isEmpty(s1))
	{
		root = peek(s1);
		push(s2, pop(s1));

		if (root->left != NULL && root->right != NULL)
		{
			push(s1, root->left);
			push(s1, root->right);
		}
		else if (root->left != NULL && root->right == NULL)
		{
			push(s1, root->left);
		}
		else if (root->left == NULL && root->right != NULL)
		{
			push(s1, root->right);
		}
	}
	while (isEmpty(s2) != 1)
	{
		printf("%d ", pop(s2)->item);
	}
}