크래프톤 정글 WEEK5 Day 38 -BST

📆24.2.14

 

오늘부로 과제 다 끝냈다 

BST 부분 어려워서 거의 다 답 보거나 GPT 돌려서 풀었다....

과제 끝내고 프로그래머스 풀고 가상 메모리 공부했땅.

 

levelOrderTraversal

 

레벨 순으로 트리를 순회하면서 노드의 값을 출력한다.

void levelOrderTraversal(BSTNode* root)
{
	Queue q;			//순회하며 방문할 노드들을 임시로 저장
	q.head = NULL;
	q.tail = NULL;

	BSTNode *temp;
	temp = 	root;

	if(temp == NULL)
		return;
	else
	{
		enqueue(&q.head, &q.tail, temp);	//루트 노드를 큐에 삽이	
		while(!isEmpty(q.head))
		{
			temp = dequeue(&q.head, &q.tail);	//큐에서 노드를 꺼내 해당 노드의 값 출력
			printf("%d ",temp->item);

			if(temp->left != NULL)
				enqueue(&q.head, &q.tail, temp->left);
			if(temp->right != NULL)
				enqueue(&q.head, &q.tail, temp->right);
		}
	}
}

 

 

inOrderIternative

 

스택을 사용하여 이진탐색 트리를 중위 순회한다. ( left -> root -> right)

void inOrderTraversal(BSTNode *root)
{
	Stack s;
	s.top = NULL;

	BSTNode *temp;
	temp = root;

	if(temp == NULL)	 return;
	
	while(1)
	{
		if(temp != NULL)
		{
			push(&s,temp);
			temp = temp->left;		//왼쪽 자식 노드 이동
		}
		else
		{
			if(!isEmpty(&s))	
			{
				temp = pop(&s);				
				printf("%d ", temp->item);
				temp= temp->right;		//이제 오른쪽 확인
			}	
			else 
				break;
		}
	}
}

 

 

preOrderIternative

 

스택을 사용하여 전위순회한다. (root -> left -> right)

void preOrderIterative(BSTNode *root)
{
	Stack s;
	s.top = NULL;

	BSTNode *temp;
	temp = root;

	if(temp == NULL) 	return;
	else
	{
		push(&s, temp);	
		
		while(!isEmpty(&s))
		{
			temp = pop(&s);
			printf("%d ", temp->item);

			if(temp->right != NULL)
				push(&s,temp->right);
			if(temp->left != NULL)
				push(&s,temp->left);
		}
	}
}

 

 

postOrderIternativeS1

 

스택을 사용해서 후위순회한다. (left -> right -> root)

 

스택의 top에 있는 노드의 오른쪽 자식 노드를 확인하고, 만약 이 오른쪽 자식 노드가 null이거나 이전에 방문했던 노드와 같다면, 스택의 top에 있는 노드를 pop하고 그 값을 출력한다.

그리고 이 노드를 이전에 방문했던 노드로 설정한다. 이 과정은 오른쪽 서브트리를 이미 방문한 후에나 루트 노드를 방문하기 위한 것이다.

만약 스택의 top에 있는 노드의 오른쪽 자식 노드가 이전에 방문한 노드와 다르다면, 현재 노드를 이 오른쪽 자식 노드로 설정한다. 이 과정은 오른쪽 서브트리를 방문하기 위한 것이다. 

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

    Stack s;
    s.top = NULL;

    BSTNode *current = root;	//현재 방문 중인 노드
    BSTNode *prev = NULL;	    //이전에 방문했던 노드

    while (current != NULL || !isEmpty(&s))
    {
        if (current != NULL)
        {
            push(&s, current);
            current = current->left;	//왼쪽 자식 노드로 이동
        }
        else
        {
            BSTNode *temp = peek(&s)->right;	//스택의 top에 있는 노드의 오른쪽 자식 노드 확인	
            if (temp == NULL || temp == prev)	
            {
                temp = pop(&s);
                printf("%d ", temp->item);
                prev = temp;
            }
            else
            {
                current = temp;
            }
        }
    }
}

 

 

postOrderIterativeS2

 

스택 2개를 사용해서 후위 순회한다

 

첫 번째 스택이 비어있지 않은 동안, 스택의 top에 있는 노드를 pop하여 두번째 스택(s2)에 push한다. 그리고 이 노드의 왼쪽 자식 노드와 오른쪽 자식 노드가 있다면, 각각 첫 번째 스택에 push한다. 이 과정을 s1이 빌 때까지 반복한다. 이렇게 하면 s2에는 노드들이 후위 순회 순서의 역순으로 저장된다.

->  s2는 후위 순회 순서대로 출력된다. 

void postOrderIterativeS2(BSTNode *root)
{
	Stack s1;
	Stack s2;
	s1.top = NULL;
	s2.top = NULL;

	BSTNode *temp;
	temp = root;

	if(temp ==NULL)	return;
	else
	{
		push(&s1,temp);		//루트 노드 push

		while(!isEmpty(&s1))
		{
			temp = pop(&s1);
			push(&s2, temp);

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