트리 순회(Tree Traversal)

트리의 모든 노드들을 방문하는 과정을 트리 순회라고 한다.
선형 자료구조(연결 리슽, 스택, 큐, ..)는 순차적으로 요소에 접근하지만 트리 자료구조는 다른 방식을 사용해야 한다.

트리를 순회할 수 있는 방법은 전위 순회, 중위 순회, 후위 순회 이렇게 세 가지가 있다.
이러한 순회는 보통 재귀로 쉽게 구현할 수 있다.

트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽이다.

전위 순회(Preorder Traversal)

깊이 우선 순회(DFT, Depth-First Traversal)이라고도 한다.

트리를 복사하거나, 전위 표기법을 구하는데 주로 사용된다.
트리를 복사할 때 전위 순회를 사용하는 이유는 트리를 생성할 때 자식 노드보다 부모 노드가 먼저 생성되어야 하기 때문이다.

위 트리의 전위 순회 결과 : A->B->D->E->C->F->G

1. 루트 노드를 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.

중위 순회(Inorder Traversal)

중위 순회는 왼쪽 오른쪽 대칭 순서로 순회를 하기 때문에 대칭 순회(Symmetric Traversal)라고도 한다.

중위 순회는 이진 탐색 트리(BST, Binary Search Tree)에서 오름차순 또는 내림차순으로 값을 가져올 때 사용한다.
내림차순으로 값을 가져오기 위해서는 역순(오른쪽-> root-> 왼쪽)으로 중위 순회를 하면 된다.

위 트리의 중위 순회 결과 : D->B->E->A->F->C->G

1. 왼쪽 서브 트리를 중위 순회한다.
2. 루트 노드를 방문한다.
3. 오른쪽 서브 트리를 중위 순회한다.

후위 순회(Postorder Traversal)

후위 순회는 주로 트리를 삭제하는 데 사용된다.
부모 노드를 삭제하기 전에 자식 노드를 삭제하는 순으로 노드를 삭제해야 하기 때문이다.

위 트리의 후위 순회 결과 : D->E->B->F->G->C->A

1. 왼쪽 서브 트리를 후위 순회한다.
2. 오른쪽 서브 트리를 후위 순회한다.
3. 루트 노드를 방문한다.

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const node = new Node(value);

    // 루트가 설정되어 있지 않다면 루트를 node로 만들어 준다. 
    // node는 treeNode()에서 뼈대를 받아온다.
    if (!this.root) {
      this.root = node;
      return this;
    }
    else {
      // 비교를 위해 current 변수를 설정해 준다.
      let current = this.root;
      // current가 true 라면 while문을 돌면서 value와 지금 현재 value인 current value를 비교한다.
      while (true) {
        // 중복된 값은 어떤 결과를 리턴하지 않는다.
        if (value === current.value) return;
        // value가 기준 value(current value)보다 작다면 왼쪽에 넣어준다.
        if (value < current.value) {
          if (!current.left) {
            current.left = node;
            break;  // return this;
          }
          else {
            // 이제 current value(기준)는 왼쪽의 data로 잡힌다.
            current = current.left;
          }
        }
        // value가 기준 value(current value)보다 크다면 오른쪽에 넣어준다.
        else if (value > current.value) {
          if (!current.right) {
            current.right = node;
            break;  // return this;
          }
          else {
            // 이제 current value(기준)는 오른쪽 value로 잡힌다.
            current = current.right;
          }
        }
      }
    }
  }

  find(value) {
    if (!this.root) return;
    let current = this.root;
    let found = false;
    while (current && !found) {
      if (value < current.value) {
        current = current.left;
      }
      else if (value > current.value) {
        current = current.right;
      }
      else {
        found = true;
      }
    }
    if (!found) return;
    return current;
  }

  // Breadth-first Search(너비 우선 탐색)
  bfs() {
    let node = this.root;
    let queue = [node];
    let data = [];

    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;
  }

  // Depth-first Search(깊이 우선 탐색)
  // 1. Pre-Order traversal(전위 순회)
  preOrder() {
    let data = [];
    function traverse(node) {
      data.push(node.value);
      if (node.left) {
        traverse(node.left);
      }
      if (node.right) {
        traverse(node.right);
      }
    }
    traverse(this.root);
    return data;
  }

  // 2. In-Order traversal(중위 순회)
  inOrder() {
    let data = [];
    function traverse(node) {
      if (node.left) {
        traverse(node.left);
        data.push(node.data);
      }
      if (node.right) {
        traverse(node.right);
      }
    }
    traverse(this.root)
    return data;
  }

  // 3. Post-Order traversal(후위 순회)
  postOrder() {
    let data = [];
    function traverse(node) {
      if (node.left) {
        traverse(node.left);
      }
      if (node.right) {
        traverse(node.right);
        data.push(node);
      }
    }
    traverse(this.root)
    return data;
  }
}

let nums = new bst();
nums.insert(10);
nums.insert(5);
nums.insert(11);
nums.insert(3);
nums.insert(6);

console.log(nums.bfs());       // 10, 5, 11, 3, 6
console.log(nums.preOrder());  // 10, 5, 3, 6, 11 
console.log(nums.inOrder());   // 3, 5, 6, 10, 11 
console.log(nums.postOrder()); // 3, 6, 5, 11, 10