Skip to content

15. Tree Traversal.md

Latest commit

 

History

History
144 lines (112 loc) · 4.67 KB

15. Tree Traversal.md

File metadata and controls

144 lines (112 loc) · 4.67 KB

Tree Traversal

트리 순회

모든 노드를 한번씩 가는 방법에 대해 알아봅시다.

순회 방법

Tree traversal - Wikibooks, open books for an open world

  1. Breadth - first Search (BFS) 맞는지 확인하기
    • F- B - G - A - D - I - C - E - H
  2. Depth - first Search (DFS) 맞는지 확인하기
    • IN Order : A B C D E F G H I
    • Preorder : F B A D C E G I H
    • Post Order : A C E D B H I G F

1. Breadth First Search (BFS)

  • 너비 우선 서칭 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

Steps

  1. 큐(First In First Out)를 만들고 방문한 노드를 담을 변수를 만듭니다.
  2. 큐를 root 노드에 위치 시킵니다.
  3. Loop 큐에 아무것도 없을때 까지
    1. Dequeue a node from the queue and push the value of the node into the variable that stores the nodes
    2. If there is a left property on the node dequeued - add it to the queue
    3. If there is a right property on the node dequeued - add it to the queue
  4. Return the variable that stores the values

implement

  BFS() {
    const data = [],
      queue = [];
    let node = this.root;
    queue.push(this.root);
    while (queue.length) {
      node = queue.shift();
      data.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    return data;
  }

2. DFS - Pre Order

Steps - 재귀적으로

  1. 방문한 노드를 담을 변수를 만듭니다.
  2. BST의 루트를 저장할 current란 변수를 만듭니다.
  3. 노드를 받을 helper function을 만듭니다.
    1. 노드의 value를 값을 저장하는 변수에 Push 합니다.
    2. if 노드의 왼쪽 프로퍼티가 존재한다면, 왼쪽 노드 프로퍼티에 helper 함수를 부릅니다.
    3. if 노드의 오른쪽 프로퍼티가 존재한다면, 오른쪽 노드 프로퍼티에 helper 함수를 부릅니다.
  4. 현재 값과 helper 함수를 불러옵니다.
  5. array를 리턴합니다.

3. DFS - Post Order

Steps - 재귀적으로

  1. 방문한 노드를 담을 변수를 만듭니다.
  2. BST의 루트를 저장할 current란 변수를 만듭니다.
  3. 노드를 받을 helper function을 만듭니다.
    1. if 노드의 왼쪽 프로퍼티가 존재한다면, 왼쪽 노드 프로퍼티에 helper 함수를 부릅니다.
    2. if 노드의 오른쪽 프로퍼티가 존재한다면, 오른쪽 노드 프로퍼티에 helper 함수를 부릅니다.
    3. 노드의 value를 값을 저장하는 변수에 Push 합니다.
    4. current 변수에 helper function을 불러옵니다
    5. array를 return 합니다.

4. DFS - In Order

Steps - 재귀적으로

  1. 방문한 노드를 담을 변수를 만듭니다.
  2. BST의 루트를 저장할 current란 변수를 만듭니다.
  3. 노드를 받을 helper function을 만듭니다.
    1. if 노드의 왼쪽 프로퍼티가 존재한다면, 왼쪽 노드 프로퍼티에 helper 함수를 부릅니다.
    2. 노드의 value를 값을 저장하는 변수에 Push 합니다.
    3. if 노드의 오른쪽 프로퍼티가 존재한다면, 오른쪽 노드 프로퍼티에 helper 함수를 부릅니다.
  4. current 변수에 helper function을 불러옵니다
  5. array를 return 합니다.

5. 전체 구현 코드

  DFSPreOrder() {
    const date = [];
    function traverse(node) {
      date.push(node.value);
      node.left && traverse(node.left);
      node.right && traverse(node.right);
    }
    traverse(this.root);
    return date;
  }
  DFSPostOrder() {
    const data = [];
    function traverse(node) {
      node.left && traverse(node.left);
      node.right && traverse(node.right);
      data.push(node.value);
    }
    traverse(this.root);
    return data;
  }
  DFSInOrder() {
    const data = [];
    function traverse(node) {
      node.left && traverse(node.left);
      data.push(node.value);
      node.right && traverse(node.right);
    }
    traverse(this.root);
    return data;
  }

6. 언제 BFS? 언제 DFS?

BFS

  1. 두 노드 사이의 최단 경로와 임의의 경로를 찾고 싶을 때 사용

DFS

  1. DFS-IN Order
    • [ 3, 6, 8, 10, 15, 20 ]
    • 작은수에서 큰수로 정렬된 값을 얻을 때 사용합니다.
  2. DFS - Pre Order
    • [ 10, 6, 15, 3, 8, 20 ]
    • Tree 구조 그대로 가져오기 때문에 파일시스템이나 데이터베이스 정보를 저장 복사 하기 좋습니다.