2025.04.13

TIL(TODAY I LEARN)

---

• 오늘한 내용 : C - BT,BST

• WEEK05: C Pointer(&, * 연산자), 동적 메모리 할당, Linked List, Stack, Queue, Binary Tree, Binary Search Tree, 동적 프로그래밍, 그리디 알고리즘

• 계속해서 C언어를 공부해보자

---

3. Binary Tree

• 이진 트리 - 자식이 둘 뿐인 트리

typedef struct _btnode{
	int item;
	struct _btnode *left;
	struct _btnode *right;
} BTNode;  

(1) indentical()

• 트리 순회의 방식?
  • 전위순회? → 재귀함수로 구현하자
    • 재귀함수? → base codition은 언제? → 노드 하나만 null or 값이 다를 때

(2) maxHeight()

• 재귀는 '작은 문제를 믿고 쓰는 구조'다
• 재귀 구현 생각 순서:

  1. 기본 상태 생각:

     → 비어 있는 트리의 높이는? → -1 (간선 수 기준)

     → → 이게 base case

  2. 작은 문제에 위임:

     → maxHeight(node->left)는 왼쪽 서브트리 높이를 구해준다

     → maxHeight(node->right)도 오른쪽 서브트리 높이를 구해준다

  3. 현재 노드는 뭘 하면 될까?

     → 왼쪽, 오른쪽 중 더 큰 쪽을 선택

     → 거기에 +1만 해주면 내 트리의 높이 완성

(3) countOneChildNodes()

• 트리 구조에서 재귀를 쓸 때 - 왼쪽 오른쪽 가지고 어떻게 해보자.
  • 왼쪽노드 리턴 결과 + 오른쪽 노드 리턴 결과 + 추가적 처리

(7) smallestValue()

• C언어에서 무한대 표현을 어떻게 해야할까?

  자료형	무한대 표현	설명
  float	INFINITY, 1.0/0.0	<math.h>
  double	HUGE_VAL, INFINITY	<math.h>
  int	INT_MAX	<limits.h>에서 상수로 정의, 가짜 무한대처럼 사용

  ---

  타입	무한대 표현 (math.h 없이)	설명
  double, float	1.0 / 0.0, -1.0 / 0.0	inf, -inf 반환됨
  int	2147483647 큰 수 직접 사용	32비트 기준 INT_MAX 값

(8) hasGreatGrandchild()

• 수정 전 코드(잘못된 코드)

int hasGreatGrandchild(BTNode *node)
{
	/* add your code here */
    if (node ==NULL)
        return -1; // 노드 없으면 높이 -1 / (간선 기준 계산).
    int left = hasGreatGrandchild(node->left);
    int right = hasGreatGrandchild(node->right);

    // 간선 수가 3개 이상이면 증손자노드가 존재.
    if (left >= 3 || right >= 3)
        printf("%d ", node->item);

    return (left > right) ? left + 1 : right + 1;
}

---

• 수정 후 코드

int hasGreatGrandchild(BTNode *node)
{
	/* add your code here */
    if (node ==NULL)
        return -1; // 노드 없으면 높이 -1 / (간선 기준 계산).
    int left = hasGreatGrandchild(node->left);
    int right = hasGreatGrandchild(node->right);
    int h = (left > right) ? left + 1 : right + 1;

    // 간선 수가 3개 이상이면 증손자노드가 존재.
    if (h >= 3)
        printf("%d ", node->item);

    return h;
}

• 수정 전 코드는 루트 높이가 3이 되었을 때 +1을 해주기 전에 프린트를 해주기 때문에 조건에서 False가 된다.
• 출력 조건을 잘 보도록 하자.

4. Binary Search Tree

(1) levelOrderTraversal()

• BFS와 같음

n = dequeue(&q.head, &q.tail);
enqueue(&q.head, &q.tail, n->left);

• head, tail은 큐의 상태를 실시간으로 바꾸는 변수 함수 안에서 바꿔야 하기 때문에 주소값을 넘겨줘야 함 (&q.head) 그래야 함수가 원본을 바꿀 수 있음 (call by reference)
  

(2) inOrderTraversal()

• 1. 일단 왼쪽 담고
  2. 팝해주면서 출력 후
  3. 오른쪽 노드로

void inOrderTraversal(BSTNode *root)
{
	/* add your code here */
	// left -> root -> right

	if (root == NULL) return;
	
	Stack stk;
	stk.top = NULL;

	BSTNode* cur = root;

	while (!isEmpty(&stk) || cur != NULL){
		
		// 일단 왼쪽 다담아
		while(cur != NULL){
			push(&stk,cur);
			cur = cur -> left;
		}
		
		// 끝이니까 팝 후 출력
		cur = pop(&stk);
		printf("%d ", cur -> item);

		//오른쪽으로
		cur = cur -> right;
	}
}

(3) preOrderTraversal()

• DFS와 같음

void preOrderIterative(BSTNode *root)
{
	 /* add your code here */
	 // root -> left -> right

	if (root == NULL) return;
	
	Stack stk;
	stk.top = NULL;

	push(&stk,root);

	BSTNode* n;
	while (!isEmpty(&stk)){
		n = pop(&stk);

		printf("%d ",n->item);

		//오른쪽을 먼저 푸시해야 왼쪽이 먼저 나옴
		if (n->right != NULL)
			push(&stk,n->right);
		if (n->left != NULL)
			push(&stk,n->left);
	}
}

---

• 중위순회와 비슷한 모양으로도 가능

void inOrderTraversal(BSTNode *root)
{
	/* add your code here */
	// left -> root -> right

	if (root == NULL) return;
	
	Stack stk;
	stk.top = NULL;

	BSTNode* cur = root;

	while (!isEmpty(&stk) || cur != NULL){
		
		// 일단 왼쪽 담는데 루트는 출력
		while(cur != NULL){
			printf("%d ", cur -> item);
			push(&stk,cur);
			cur = cur -> left;
		}
		
		// 끝이니까 팝
		cur = pop(&stk);

		//오른쪽으로
		cur = cur -> right;
	}
}

---

• 이제 이번 주 주어진건 BST 4, 5번 남았다.
  얼른 풀고 개념공부하고싶다.
  될 거 같은데 생각보다 어려운듯.