[자료구조] BFS: Level Order Traversal

혜써클이 떴습니다☀️·2024년 11월 5일

자료구조 및 알고리즘

목록 보기

5/8

노드 접근 방식

1. Deth-First(Traversal/Search)(DFS: 깊이 우선 탐색)

Inorder Traversal
Postorder Traversal
Preorder Traversal

2. Breadth-First(Traversal/Search)(BFS: 너비 우선 탐색)

Level Order Traversal

Level Order Traversal

같은 level에 있는 노드 먼저 탐색

알고리즘)
1. 트리의 높이(height) 구하기
2. 각 레벨의 현재 높이를 유지하면서 재귀 함수 실행
3. 노드의 레벨이 일치할 때마다 해당 노드 출력

1. 스택 이용

// javascript
class Node {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}

function printLevelOrder(root) {
    var h = height(root);
    for (var i = 1; i <= h; i++)
        printCurrentLevel(root, i);
}

// 현재 level 확인
function printCurrentLevel(root, level) {
    if (root == null)
        return;
    if (level == 1)
        console.log(root.data + " ");
    else if (level > 1) {
      	// 왼쪽으로 이동한 후,level을 낮추고 재귀함수
        printCurrentLevel(root.left, level - 1);
      	// 오른쪽으로 이동한 후,level을 낮추고 재귀함수
        printCurrentLevel(root.right, level - 1);
    }
}

// 트리의 height 계산하기
function height(root) {
    if (root == null)
        return 0;
    else {
        var lheight = height(root.left);
        var rheight = height(root.right);
      	// 길이가 더 긴 서브 트리의 길이 + 1
        if (lheight > rheight)
            return (lheight + 1);
        else
            return (rheight + 1);
    }
}

root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

printLevelOrder(root); // 1 2 3 4 5

Time Complexity: O(N^2) (N:비대칭 트리의 노드 수)
Auxiliary Space: O(N) 사용된 재귀 스택 공간은 O(N)

2. 큐 이용

// JavaScript
class Node {
    constructor(key) {
        this.data = key;
        this.left = null;
        this.right = null;
    }
}

function printLevelOrder(root) {

    if (root === null) return;

    const queue = [];

    // 현재 노드값 큐에 추가
    queue.push(root);

    while (queue.length > 0) {
      	// 큐의 시작점을 출력하고 삭제
        const node = queue.shift();
        console.log(node.data);

        // 왼쪽 자식 노드값 큐에 추가
        if (node.left !== null) {
            queue.push(node.left);
        }
      	// 오른쪽 자식 노드값 큐에 추가
        if (node.right !== null) {
            queue.push(node.right);
        }
    }
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

printLevelOrder(root); // 1 2 3 4 5