크래프톤 정글 week05, day38 - 연휴 과제 - 이진 트리, 이진 탐색 트리

이진 트리 문제

• 두 개의 트리의 구조와 값이 같은지 확인하는 함수(문제에 값은 안나와있었지만 첨부)

int identical(BTNode *tree1, BTNode *tree2)

{
    // 만약 두 트리가 탐색할 노드가 없다면 같다고 판단해 1 반환
    if(tree1 == NULL && tree2 == NULL) return 1;
    // 위의 if문 통과 후 하나라도 탐색할 노드가 남아있다면 두 트리가 달라 0 반환
    if(tree1 == NULL || tree2 == NULL) return 0;

    return (
        // tree1의 값과 tree2의 값이 같고
        tree1->item == tree2->item &&
        // 노드 왼쪽 노드로 재귀를 타고
        identical(tree1->left, tree2->left) &&
        // 오른쪽 노드까지 재귀가 다 끝나면 동일한 것으로 판단해 1반환
        // 동일하지 않으면 애초에 재귀를 돌며 위의 if문에서 걸림
        identical(tree1->right, tree2->right) 
    );
}

 

 

• 트리의 제일 끝 높이가 몇인지 확인하는 함수

int maxHeight(BTNode *node)

{
    // 더이상 내려갈 노드가 없다면 -1을 리턴
    // (pdf에서 루트 노드를 높이로 안세서 -1로 시작)
    if(node == NULL) {
        return -1;
    // 자식 노드를 검사
    } else {
        // 왼쪽 높이에 왼쪽노드로 재귀를 돌린 리턴값을 넣기
        int leftHeight = maxHeight(node->left);
        // 오른쪽 높이에 오른쪽노드로 재귀를 돌린 리턴값을 넣기
        int rightHeight = maxHeight(node->right);

        // 만약 왼쪽높이가 오른쪽 높이보다 크면 왼쪽높이에+1 리턴
        if(leftHeight > rightHeight) return leftHeight+1;
        // 오른쪽높이가 더 크면 오른쪽높이에+1 리턴
        else return rightHeight+1;
    }
}

 

 

• 자식 노드가 왼쪽이든 오른쪽이든 한 개만 가지고 있는 노드의 개수를 찾는 함수

int countOneChildNodes(BTNode *node)

{
    // 탐색할 노드가 없을 때 0 리턴
    if(node == NULL) {
        return 0;
    // 탐색할 노드가 남아있을 때
    } else {
        // 개수를 셀 변수를 선언해주고
        int count = 0;
        // 만약 왼쪽노드만 있거나 오른쪽 노드만 있을 때 카운트를 증가시킨다.
        if((node->left == NULL && node->right != NULL) || 
        (node->left != NULL && node->right == NULL)) {
            count = 1;
        }
        // 그리고 노드의 왼쪽 방향과 오른쪽 방향으로 재귀를 돌며 저장된
        // count에 기존의 count를 합쳐 재귀를 다 돌았을 때의 개수를 리턴
        return count + countOneChildNodes(node->left) + 
        countOneChildNodes(node->right);
    }
}

 

 

• 트리를 다 돌면서 노드의 값이 홀수인 노드들을 전부 합하는 함수

int sumOfOddNodes(BTNode *node)

{
    // 더이상 탐색할 노드가 없다면 0 리턴
    if(node == NULL) {
        return 0;
    // 탐색할 노드가 있다면
    } else {
        // 홀수 합산 값을 담기 위한 변수를 선언
        int odd = 0;
        // 만약 현재 노드의 값이 홀수라면 변수에 값 합치기
        if(node->item % 2 == 1) {
            odd += node->item;
        }
        // 노드의 왼쪽부터 재귀를 돌며 홀수가 있으면 변수에 값 넣기
        odd += sumOfOddNodes(node->left);
        // 왼쪽이 끝나면 오른쪽으로 돌며 홀수가 있으면 변수에 값 넣기
        odd += sumOfOddNodes(node->right);

        // 재귀가 다 끝나고 합친 값을 리턴
        return odd;
    }
}

 

 

• 트리의 좌우를 뒤바꾸는 함수

void mirrorTree(BTNode *node)
{
    // 더이상 탐색할 노드가 없으면 return
    if(node == NULL) return;

    // 함수를 왼쪽부터 오른쪽 까지 노드로 재귀를 돌리기
    mirrorTree(node->left);
    mirrorTree(node->right);

    // swap 개념
    // 임시 노드 변수를 만들고 노드의 왼쪽 자식 노드를 저장해놓기
    BTNode *tempNode = node->left;
    // 노드 왼쪽자식값 저장했으니 오른쪽 자식값으로 변경
    node->left = node->right;
    // 노드 오른쪽자식값 저장했으니 왼쪽값 있는 temp변수 값 넣기
    node->right = tempNode;
}

 

 

• 트리의 노드 중 입력한 값보다 작은 노드들을 전부 출력하는 함수

void printSmallerValues(BTNode *node, int m)
{
    // 탐색할 노드가 없다면 리턴
	if(node == NULL) {
        return;
    // 있다면 
    } else {
        // 문제에는 전위순회로 출력되기 때문에 전위순회로 작성
        // 노드 값이 지정한 값보다 작으면 출력
        if(node->item < m) {
            printf("%d ", node->item);
        }
        // 재귀하며 값을 확인
        printSmallerValues(node->left, m);
        printSmallerValues(node->right, m);
    }
}

 

 

• 트리의 노드들 중 가장 작은 값을 가진 노드를 찾는 함수

int smallestValue(BTNode *node)
{
    // 탐색할 노드가 없으면
	if(node == NULL) {
        // 10000을 리턴(지피티 코드로는 가장 큰값을 넣으라고 함)
        return 10000;
    // 탐색할 노드가 있으면
    } else  {
        // 현재 노드값을 변수에 담고
        int bumo = node->item;
        // 왼쪽과 오른쪽을 각 인자로 받아 재귀
        int left = smallestValue(node->left);
        int right = smallestValue(node->right);

        // 만약 현재 노드가 왼쪽과 오른쪽보다 작으면
        if((left > bumo) && (right > bumo)) {
            // 현재 노드 리턴
            return bumo;
        // 그게 아니라 왼쪽이 더 작으면
        } else if (left < right) {
            // 왼쪽 리턴
            return left;
        // 오른쪽이 더 작으면
        } else {
            // 오른쪽 리턴
            return right;
        }
    }
}

 

 

• 손자 노드를 가진 노드들을 찾는 함수(본인보다 2단계 이상의 밑 자식 노드들이 있는지 확인)

int hasGreatGrandchild(BTNode *node)
{
    // 탐색할 노드가 없으면 리턴
	if(node == NULL) return;

    // 만약 노드 왼쪽노드가 존재하고 그 밑자식이 하나라도 있으면
    if(node->left != NULL && (node->left->left != NULL || node->left->right != NULL)) {
        // 그 노드의 값을 출력하고 1 리턴
        printf("%d", node->item);
        return 1;
    }

    // 만약 노드의 오른쪽 자식이 존재하고 그 밑자식이 하나라도 있으면
    if (node->right != NULL && (node->right->left != NULL || node->right->right != NULL))
    {
        // 그 노드 값을 출력하고 1 리턴
        printf("%d ", node->item);
        return 1;
    }

    // 노드의 왼쪽자식과 오른쪽 자식을 인자로 재귀를 돌려서 손자 노드가 있는지 확인 후 리턴
    return hasGreatGrandchild(node->left) || hasGreatGrandchild(node->right);
}

---

이진 탐색 트리 문제

• 레벨 순회방식으로 이진탐색트리 구현(BFS 처럼 차수 별로 순서대로 출력하는 순회방식)

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

	// 추가와 삭제를 담당하는 포인터를 초기화한다.
	QueueNode *head = NULL;
	QueueNode *tail = NULL;
	// 
	enqueue(&head, &tail, root);

	// 큐가 빌 때까지 반복
	while (!isEmpty(head)) {
		// 큐에서 노드를 하나 꺼내고 그 노드의 값을 출력
		BSTNode *node = dequeue(&head, &tail);
		printf("%d ", node->item);

		// 방문한 노드의 왼쪽 자식이 있다면 큐에 넣기
		if (node->left != NULL)
			enqueue(&head, &tail, node->left);
		// 방문한 노드의 오른쪽 자식이 있다면 큐에 넣기
		if (node->right != NULL)
			enqueue(&head, &tail, node->right);
	}
}

 

 

• 중위 순회 방식으로 이진 탐색 트리 구현

void inOrderTraversal(BSTNode *root)
{
	// 노드가 비어잇으면 리턴
	if(root == NULL) {
		return;
	// 비어있지 않으면 중위 순회
	} else {
		inOrderTraversal(root->left);
		printf("%d ", root->item);
		inOrderTraversal(root->right);
	}
}

 

 

• 스택을 사용해 전위순회 방식으로 이진 탐색 트리 구현

void preOrderIterative(BSTNode *root)
{
	// 스택을 선언하고 맨 앞 값을 초기화
	Stack stack;
	stack.top = NULL;

	// 만약 값이 NULL이라면 리턴
	if(root == NULL) return;

	// 맨 앞의 루트노드를 스택에 넣기
	push(&stack, root);

	// 스택이 빌 때까지 반복하며
	while(!isEmpty(&stack)) {
		//(전위 순회)
		// 스택에서 삭제한 값을 node에 담고 노드의 값 출력
		BSTNode *node = pop(&stack);
		printf("%d ", node->item);

		// 노드의 오른쪽 자식이 있으면 그 노드 스택에 넣기
		// 스택은 거꾸로 출력되기 때문에 반대로 오른쪽부터 출력
		if(node->right != NULL) {
			push(&stack, node->right);
		}
		// 노드의 왼쪽 자식이 있으면 그 노드 스택에 넣기
		if(node->left != NULL) {
			push(&stack, node->left);
		}
	}
}

 

 

• 스택을 사용해 후위 순회 방식으로 이진 탐색 트리 구현

void postOrderIterativeS1(BSTNode *root)
{
	// 스택을 선언하고 맨 앞 값을 초기화
	Stack stack;
	stack.top = NULL;

	// 만약 값이 NULL이라면 리턴
	if(root == NULL) return;

	// 맨 앞의 루트노드를 스택에 넣기
	push(&stack, root);

	// 스택이 빌 때까지 반복하며
	while(!isEmpty(&stack)) {
		//(후위 순회)
		// 스택에서 삭제한 값을 node에 담기
		BSTNode *node = pop(&stack);

		// 노드의 오른쪽 자식이 있으면 그 노드 스택에 넣기
		// 스택은 거꾸로 출력되기 때문에 반대로 오른쪽부터 출력
		if(node->right != NULL) {
			push(&stack, node->right);
		}
		// 노드의 왼쪽 자식이 있으면 그 노드 스택에 넣기
		if(node->left != NULL) {
			push(&stack, node->left);
		}
		// 노드의 값 출력
		printf("%d ", node->item);
	}
}

 

 

• 스택을 2개를 이용해 후위 순회 방식으로 이진 탐색 트리를 구현

void postOrderIterativeS2(BSTNode *root)
{
	// 스택1과 스택2를 선언하고 맨 앞 값을 초기화
	Stack stack1;
	stack1.top = NULL;
	Stack stack2;
	stack2.top = NULL;  

	// 만약 값이 NULL이라면 리턴
	if(root == NULL) return;

	// 맨 앞의 루트노드를 스택1에 넣기
	push(&stack1, root);

	// 스택1이 빌 때까지 반복하며
	while(!isEmpty(&stack1)) {
		//(후위 순회)
		// 스택1에서 삭제한 값을 node에 담고
		BSTNode *node = pop(&stack1);
		// 삭제한 값을 스택2에 넣기
		push(&stack2, node);
		// 노드의 왼쪽자식이 있다면 스택1에 넣기
		if(node->left) {
			push(&stack1, node->left);
		}
		// 노드의 오른쪽 자식이 있다면 스택1에 넣기
		if(node->right) {
			push(&stack1, node->right);
		}
	}

	// 스택2가 빌때까지 노드변수에 스택2를 담아 출력
	while(!isEmpty(&stack2)) {
		BSTNode *node = pop(&stack2);
		printf("%d ", node->item);
	}
}

 

연휴 과제 턱걸이로 끝내고 내일부턴 다시 malloc을 위한 공부 키워드 학습과 c언어 공부 시작

​

 

학습 시간 : 10 ~ 26시