*참고로 Post-order 방법은 다소 복잡하여 이전 포스팅에서 따로 다뤘다.

Level order Traversal

: 루트부터 루트와 가까운 노드를 차례대로 순회하는 방법

: 레벨을 하나씩 늘려가며 방문한다.

Stack 코드

void levelOrderTraversal(BSTNode *root)
{
	/* add your code here */
	QueueNode *head = NULL;
	QueueNode *tail = NULL;

	enqueue(&head, &tail, root);
	BSTNode *cur;

	while (head != NULL)
	{
		cur = dequeue(&head, &tail);
		printf("%d ", cur->item);

		// 자식 노드 큐에 추가
		if (cur->left)
			enqueue(&head, &tail, cur->left);
		if (cur->right)
			enqueue(&head, &tail, cur->right);
	}
}

In-order Traveral

: 중위 순회 방법으로 루트를 중간에 방문한다.
: 왼쪽 자식, 루트, 오른쪽 자식 순서로 방문한다.

Recursive 구현

void inOrderTraversal(BSTNode *root)
{
    if (root == NULL)
        return;

    inOrderTraversal(root->left);       // 왼쪽 자식
    printf("%d ", root->item);          // 루트 
    inOrderTraversal(root->right);      // 오른쪽 자식
}

Stack 구현

void inOrderTraversal(BSTNode *root)
{
	/* add your code here */
	Stack *stack = (Stack *)malloc(sizeof(Stack));
	stack->top = NULL;

	BSTNode *cur = root;

	while (cur != NULL || !isEmpty(stack))
	{
		// 왼쪽 자식 끝까지 추가
		while (cur != NULL)
		{
			push(stack, cur);
			cur = cur->left;
		}

		// 이제 left 노드가 leaf에 도달
		cur = pop(stack);
		printf("%d ", cur->item);

		// 오른쪽 노드
		cur = cur->right;
	}
}

Pre-order Traveral

: 전위 순회 방법으로 루트를 가장 먼저 방문한다.
: 루트, 왼쪽 자식, 오른쪽 자식 순서로 방문한다.

Recursive 구현

void preOrderTraversal(BSTNode *root)
{
    if (root == NULL)
        return;

    printf("%d ", root->item);          // 루트
    preOrderTraversal(root->left);      // 왼쪽 자식
    preOrderTraversal(root->right);     // 오른쪽 자식
}

Stack 구현

void preOrderIterative(BSTNode *root)
{
	/* add your code here */
	Stack *stack = (Stack *)malloc(sizeof(Stack));
	stack->top = NULL;

	BSTNode *cur = root;
	push(stack, cur);

	while (!isEmpty(stack))
	{
		cur = pop(stack);
		printf("%d ", cur->item); // 부모 노드 방문

		if (cur->right) // 오른쪽 자식 나중에 방문
			push(stack, cur->right);
		if (cur->left) // 왼쪽 자식 우선 방문
			push(stack, cur->left);
	}
}