[정글 WEEK05_C언어, 자료구조] Binary Tree 1번_levelOrderTraversal

TODO

1. 이진 탐색 트리를 레벨 순으로 순회하기(levelOrderTraversal)

---

📦 구조체 분석

1. BSTNode

: 이진 트리를 구성하는 노드

   - item: 노드가 가지고 있는 int 타입 데이터

   - left: 왼쪽 자식 노드를 가리키는 포인터

   - right: 오른쪽 자식 노드를 가리키는 포인터

typedef struct _bstnode {
    int item;
    struct _btnode *left;
    struct _btnode *right;
} BSTNode;

 

2. QueueNode

: BSTNode를 wrapping해서 연결리스트 형태로 큐를 구성하기 위한 노드

   - data: 이진트리의 한 노드(BSTNode)를 가리키는 포인터

   - nextPtr: 큐에서 다음 QueueNode를 가리키는 포인터

typedef struct _queueNode {
    BTNode *data;
    struct _queueNode *nextPtr;
} QueueNode;

 

3. Queue

: 이진 탐색 트리 노드들의 방문 순서를 관리하는 큐 

   - head: 첫 번째 QueueNode

   - tail: 마지막 QueueNode

typedef struct _queue {
    QueueNode *head;
    QueueNode *tail;
} Queue;

 

 

🪄 기존 함수 분석

insertBSTNode(BSTNode **node, int value): 이진 탐색 트리에 value를 값으로 가지는 노드 삽입

 

dequeue(QueueNode **head, QueueNode **tail): 트리 노드의 head에 있는 QueueNode를 큐에서 삭제

enqueue(QueueNode **head, QueueNode **tail, BSTNode *node): 새 QueueNode를 만들고, 트리 노드를 큐에 tail쪽에 삽입

isEmpty(QueueNode *head): 큐가 비었는지 확인

removeAll(BSTNode **node): 후위 순회 방식(왼쪽 → 오른쪽 → 루트)으로 노드 하나하나씩 메모리에서 해제

 

 

⚡️ 이진 트리를 레벨 순으로 순회하기

pseudocode

1. 큐를 초기화한다.

2. 루트 노드를 큐에 삽입한다.

3. 큐가 비기 전까지 아래 로직을 반복한다.

  3-1) 현재 노드를 dequeue() 한다.

  3-2) 현재 노드의 값을 출력한다.

  3-3) 만약 curr의 왼쪽 자식이 있다면 왼쪽 자식을 enqueue() 한다.

  3-4) 만약 curr의 오른쪽 자식이 있다면 오른쪽 자식을 enqueue() 한다. 

 

⌨️ 구현

void levelOrderTraversal(BSTNode* root)
{
    /*
	큐로 구현한 이진 트리를 level-by-level로 순회한 결과를 출력한다!
	큐에 노드 추가/삭제 시 enqueue()와 dequeue()만 사용할 수 있다.
	큐는 NULL로 초기화 후 사용해야 한다.
	*/
	if (root == NULL) return;

	QueueNode *head = NULL;
	QueueNode *tail = NULL;

	enqueue(&head, &tail, root);

	while (!isEmpty(head)) {
		BSTNode *curr = dequeue(&head, &tail);
		
		printf("%d ", curr->item);

		if (curr->left != NULL) {
			enqueue(&head, &tail, curr->left);
		}

		if (curr->right != NULL) {
			enqueue(&head, &tail, curr->right);
		}
	}
}