[Jungle][TIL] 240417 Binary Search Trees(BST) - (1)

이진 탐색 트리 (Binary Search Trees, BST)

이진 탐색(binary search) + 연결 리스트(linked list)

• 각 노드의 왼쪽 서브트리에는 해당 노드 값 보다 작은 값을 지닌 노드들
• 각 노드의 오른쪽 서브트리에는 해당 노드 값 보다 큰 값을 지닌 노드들을 가진다.
• 중복된 노드가 없어야 한다.

void levelOrderTraversal(BSTNode *root)
: 레벨별로 노드 출력 -> BFS 방식으로 출력

출력 결과: 20 15 50 10 18 25 80

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

	Queue *queue;
    queue = malloc(sizeof(Queue));
    
    //메모리 동적 할당 실패시 return 으로 함수 종료
    if (queue == NULL) {
    	return ;
    }
    
    queue->head = NULL;
    queue->tail = NULL;
	
    // 큐에 루트 노드 enqueue
	enqueue(&queue-> head, &queue-> tail, root); 
    
    //큐가 빌 때까지 반복
    while (!isEmpty(queue->head)) {
    	BSTNode *deq = dequeue(&queue-> head, &queue->tail);
        //큐에서 노드를 꺼내서 출력
        printf("%d ", deq->item);
    	
        //왼쪽 자식이 있다면 Queue에 추가 - enqueue
        if (deq->left != NULL) {
        	enqueue(&queue -> head, &queue-> tail, deq-> left);
        }
        
        //오른쪽 자식이 있다면 Queue에 추가 - enqueue
        if (deq->right != NULL) {
        	enqueue(&queue-> head, &queue->tail, deq-> right); 
        }
    }
    
 	free(queue);   
 }
}

루트 노드인 20 큐에 추가
큐에서 20 꺼내서 출력
왼쪽 자식인 15 큐에 추가. enqueue
오른쪽 자식인 50 큐에 추가 enqueue
현재 큐의 상태 [15, 50]

---

큐에서 15 꺼내서 출력
왼쪽 자식 10 enqueue
오른쪽 자식 18 enqueue
현재 큐의 상태 [50, 10, 18]

---

큐에서 50 꺼내서 출력
왼쪽 자식 25 enqueue
오른쪽 자식 80 enqueue
현재 큐의 상태 [10, 18, 25, 80]

---

큐에서 10 꺼내서 출력
자식 노드 없으니 다음 노드 18 출력
자식 노드 없으니 다음 노드 25 출력
자식 노드 없으니 다음 노드 80 출력