오늘 배운 것들

1. 연습문제(계속)

1-1. 이진탐색트리 2번(중위순회)

void inOrderTraversal(BSTNode *root)
{
	Stack s;
    BSTNode *cur, *prev;

    if (root == NULL) return;

    s.top = NULL;
    cur = NULL;
    prev = root;
    
    push(&s, root);
    while(!isEmpty(&s)) {
        cur = pop(&s);
        // 말단노드일 때
        if (cur->left == NULL && cur->right == NULL) {
            printf("%d ", cur->item);
        }
        // 왼쪽 서브트리의 순회를 마친 노드일 때
        else if ((peek(&s) != NULL && cur->right == peek(&s)) || (prev != NULL && cur->left == prev)) {
            printf("%d ", cur->item);
        }
        // 그 외의 경우
        else {
            if (cur->right != NULL) push(&s, cur->right);
            push(&s, cur);
            if (cur->left != NULL) push(&s, cur->left);
        }
        if (prev != NULL && prev->right != cur) prev = cur;
    }
}

이진탐색트리를 스택을 이용하여 중위순회하는 문제.(재귀 없이)
이진탐색트리는 왼쪽 서브트리에 루트 노드보다 작은 노드를, 오른쪽 서브트리에 큰 노드를 배치하므로 중위순회를 하면 오름차순으로 방문한다.

중위순회는 왼쪽 서브트리 - 루트 노드 - 오른쪽 서브트리 순으로 순회하므로
오른쪽 노드 - 루트 노드 - 왼쪽 노드 순으로 스택에 넣으며 진행한다.
왼쪽 순회를 마친 경우(prev->right != cur)나 말단 노드인 경우에는 출력한다.
prev에는 최근에 순회한 왼쪽 노드를 저장한다.

개선

void inOrderTraversal(BSTNode *root)
{
	Stack s;
	BSTNode *cur;
	s.top = NULL;
    
    if (root == NULL) return;
	
	push(&s, root);
	while (!isEmpty(&s))
	{
    	// 왼쪽으로 계속 진행
		if (cur != NULL) {
			push(&s, cur);
			cur = cur->left;
		}
		else {
			cur = pop(&s);
			printf("%d ", cur->item);
			cur = cur->right;
		}
	}
}

다른 코드를 보니 더 간단하게 구현이 가능했다.
왼쪽 끝까지 방문한 후 왼쪽 노드가 없으면 오른쪽 노드를 찾아 진행하는 순서를 맞춰서 순회하면 간단하다.

1-2. 이진탐색트리 4번(후위순회)

void postOrderIterativeS1(BSTNode *root)
{
	Stack s;
    BSTNode *cur, *prev;
    
    if (root == NULL) return;

    s.top = NULL;
    cur = NULL;
    prev = NULL;
    
    push(&s, root);
    while(!isEmpty(&s)) {
        cur = pop(&s);
        if (cur->left == NULL && cur->right == NULL) {
            printf("%d ", cur->item);
        }
        else if (prev != NULL && (cur->right == prev || cur->left == prev)) {
            printf("%d ", cur->item);
        }
        else {
            push(&s, cur);
            if (cur->right != NULL) push(&s, cur->right);
            if (cur->left != NULL) push(&s, cur->left);
        }
        prev = cur;
    }
}

이진탐색트리를 스택을 이용하여 후위순회하는 문제.(재귀 없이)

후위순회는 루트노드를 방문하기 직전 자식노드를 반드시 방문한다는 것에 아이디어를 얻어
중위순회의 문제에서 조건만 약간 변경했다.

개선

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

	BSTNode *cur = root;
	BSTNode* pre = NULL;
	BSTNode *visited = NULL;
	Stack s;
	s.top = NULL;

	while (!isEmpty(&s) || cur != NULL)
	{
		if(cur != NULL){
			push(&s, cur);
			cur = cur->left;
		}
		else{
			pre = peek(&s);
			if(pre->right != NULL && pre->right != visited){
				cur = pre->right;
			}
			else{
				visited = pop(&s);
				printf("%d ", visited->item);
				cur = NULL;
			}
		}
	}
}

이 코드도 마찬가지로 위와 같이 개선이 가능하다.