[C언어] Binary Search Tree (1) - levelOrderTraversal 함수 구현하기

Binary Search Tree (1) - levelOrderTraversal 함수 구현하기

이진 탐색 트리의 레벨 순서 순회를 큐를 사용하여 반복문으로 구현하고, 순회 결과를 출력하는 함수

주어진 요소 확인하기

구조체

• BSTNode: (struct) 이진 탐색 트리 노드 구조체
  • item: (int field) 노드의 값
  • *left: (pointer field) 왼쪽 자식 노드 주소
  • *right: (pointer field) 오른쪽 자식 노드 주소

• QueueNode: (struct) 큐 노드 구조체
  • *data: (pointer field) 이진 탐색 트리 노드 주소
  • *nextPtr: (pointer field) 다음 큐 노드 주소

• Queue: (struct) 큐 구조체
  • *head: (pointer field) 큐 맨 앞 노드 주소
  • *tail: (pointer field) 큐 맨 뒤 노드 주소

levelOrderTraversal 함수의 매개 변수

• *node: (pointer) 이진 탐색 트리 루트 노드 주소

 

핵심 아이디어

• 루트 노드가 NULL이면 return
• 큐에 루트 노드를 넣고 큐가 빌 때까지 돌아가는 반복문을 연다.
  • 큐에서 노드 하나를 꺼내고, 해당 노드의 값을 출력한다.
  • 이후 노드의 좌우 자식이 있는 경우 왼쪽 자식, 오른쪽 자식 순서대로 큐에 넣는다.

 

구현하기

// 이진 탐색 트리의 레벨 순서 순회를 큐를 사용하여 반복문으로 구현하고, 순회 결과를 출력하는 함수
void levelOrderTraversal(BSTNode* root) {
    // 트리가 비어 있으면 return
	if (root == NULL) return;

    // 임시 큐 생성 및 초기화 (동적 할당 없이 사용)
	Queue q;
	q.head = NULL;
	q.tail = NULL;

    // 루트 노드를 큐에 삽입
	enqueue(&q.head, &q.tail, root);

    // 큐가 빌 때까지 반복
	while (!isEmpty(q.head)) {
        // 큐에서 노드 하나를 꺼내기
		BSTNode *node = dequeue(&q.head, &q.tail);

        // 해당 노드의 값을 출력
		printf("%d ", node->item);

        // 왼쪽 자식이 존재하면 큐에 추가
		if (node->left)
			enqueue(&q.head, &q.tail, node->left);
        // 오른쪽 자식이 존재하면 큐에 추가
		if (node->right)
			enqueue(&q.head, &q.tail, node->right);
	}
}