[JS] 재귀 함수 2 - 트리 순회

✨ 트리 순회

트리 순회는 트리 자료구조에서 각 노드를 한 번씩 탐색하는 알고리즘이다.

트리 순회는 여러 방법이 있지만 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder)는 재귀를 이용할 수 있다.

모든 순회는 루트 노드부터 시작하며, 어떤 노드를 먼저 방문하는지가 달라진다.

 

 

1. 전위 순회 (Preorder)

먼저 노드를 방문한 후 왼쪽 서브 트리를 전위 순회한 다음에 오른쪽 서브 트리를 전위 순회하는 방식이다.

아래와 같은 이진 트리가 있다고 가정해 보자.

1. 1을 방문한 후, 1의 왼쪽 서브 트리로 이동한다.
2. 2를 방문한 후, 2의 왼쪽 서브 트리로 이동한다.
3. 4를 방문한 후, 왼쪽과 오른쪽 서브 트리가 없기 때문에 다시 올라가서 2의 오른쪽 서브 트리로 이동한다.
4. 5를 방문한 후, 왼쪽과 오른쪽 서브 트리가 없기 때문에 다시 올라가고, 왼쪽과 오른쪽 서브 트리를 모두 방문했기 때문에 다시 올라간다.
5. 1의 오른쪽 서브트리로 이동한다.
6. 3을 방문한 후, 3의 왼쪽 서브 트리로 이동한다.
7. 6을 방문한 후, 왼쪽과 오른쪽 서브 트리가 없기에 다시 올라가서 3의 오른쪽 서브 트리로 이동한다.
8. 7을 방문한 후, 7의 왼쪽 서브 트리로 이동한다.
9. 8을 방문한 후, 왼쪽과 오른쪽 서브 트리가 없기 때문에 다시 올라간다. 
10. 7의 오른쪽 서브 트리로 이동하여 9를 방문한다.
11. 모든 트리를 순회했기에 종료된다.

최종적으로 1, 2, 4, 5, 3, 6, 7, 8, 9 노드 순으로 방문을 하게된다.

preorder(tree) {
  방문(tree.root);
  preorder(tree.left);
  preorder(tree.right);
}

의사 코드로 나타내면 이렇게 표현할 수 있다.

 

 

2. 중위 순회 (Inorder)

왼쪽 서브 트리를 중위 순회한 후 노드를 방문한 다음에 오른쪽 서브 트리를 중위 순회한다.

1. 1의 왼쪽 서브 트리로 이동, 2의 왼쪽 서브 트리로 이동, 더 이상 왼쪽 서브 트리가 없으므로 4를 방문한다.
2. 4의 오른쪽 서브트리가 없으므로 올라간 후 2를 방문한다.
3. 2의 오른쪽 서브트리로 이동, 더 이상 왼쪽 서브트리가 없으므로 5를 방문한다.
4. 5의 오른쪽 서브 트리가 없으므로 올라간 후, 2에서 왼쪽과 오른쪽 서브 트리를 모두 방문했기에 다시 올라간 후 1을 방문한다.
5. 1의 오른쪽 서브 트리로 이동, 3의 왼쪽 서브트리로 이동, 더 이상 왼쪽 서브 트리가 없으므로 6을 방문한다.
6. 6의 오른쪽 서브 트리가 없기에 올라간 후 3을 방문한다.
7. 3의 오른쪽 서브 트리로 이동, 7의 왼쪽 서브 트리로 이동, 더 이상 왼쪽 서브 트리가 없기에 8을 방문한다.
8. 8의 오른쪽 서브 트리가 없기에 올라간 후 7을 방문한다.
9. 7의 오른쪽 서브 트리로 이동, 더 이상 왼쪽 서브 트리가 없어 9를 방문한다.
10. 모든 트리를 순회했기에 종료된다.

최종적으로 4, 2, 5, 1, 6, 3, 8, 7, 9 노드 순으로 방문을 하게 된다.

inorder(tree) {
  inorder(tree.left);
  방문(tree.root);
  inorder(tree.right);
}

의사 코드로 나타내면 이렇게 표현할 수 있다.

 

 

3. 후위 순회 (Postorder)

왼쪽 서브 트리를 후위 순회 한 후 오른쪽 서브 트리를 후위 순회한 다음에 노드를 방문하는 방식이다.

1. 1의 왼쪽 서브 트리로 이동, 2의 왼쪽 서브 트리로 이동, 더 이상 왼쪽과 오른쪽 서브 트리가 없어 4를 방문한다.
2. 올라간 후, 2의 오른쪽 서브 트리로 이동, 더 이상 왼쪽과 오른쪽 서브 트리가 없어 5를 방문한다.
3. 모든 서브 트리를 방문하였기에 2를 방문한다.
4. 올라간 후, 1의 오른쪽 서브 트리로 이동, 3의 왼쪽 서브 트리로 이동, 더 이상 왼쪽과 오른쪽 서브 트리가 없어 6을 방문한다.
5. 올라간 후, 3의 오른쪽 서브 트리로 이동, 7의 왼쪽 서브 트리로 이동, 더 이상 왼쪽과 오른쪽 서브 트리가 없어 8을 방문한다.
6. 올라간 후, 7의 오른쪽 서브 트리로 이동, 더 이상 왼쪽과 오른쪽 서브 트리가 없어 9를 방문한다.
7. 올라간 후, 더 이상 왼쪽과 오른쪽 서브 트리가 없어 7을 방문한다.
8. 올라간 후, 더 이상 왼쪽과 오른쪽 서브 트리가 없어 3을 방문한다.
9. 올라한 후, 더 이상 왼쪽과 오른쪽 서브 드리가 없어 1을 방문한다.

최종적으로 4, 5, 2, 6, 8, 9, 7, 3, 1 노드 순으로 방문을 하게 된다.

postorder(tree) {
  postorder(tree.left);
  postorder(tree.right);
  방문(tree.root);
}

의사 코드로 나타내면 이렇게 표현할 수 있다.

 

 

---

✨ JS 구현 코드

전위, 중위, 후위 순회에 대한 재귀 코드 구현은 다음과 같다.

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

class Tree {
  constructor(node) {
    this.root = node;
  }

  preorder(currentNode) { // 전위 순회
    console.log(currentNode.value);
    if (currentNode.left) this.preorder(currentNode.left);
    if (currentNode.right) this.preorder(currentNode.right);
  }

  inorder(currentNode) { // 중위 순회
    if (currentNode.left) this.inorder(currentNode.left);
    console.log(currentNode.value);
    if (currentNode.right) this.inorder(currentNode.right);
  }

  postorder(currentNode) { // 후위 순회
    if (currentNode.left) this.postorder(currentNode.left);
    if (currentNode.right) this.postorder(currentNode.right);
    console.log(currentNode.value);
  }
}

const tree = new Tree(new Node(9));
tree.root.left = new Node(3);
tree.root.right = new Node(8);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(7);
tree.root.left.right.right = new Node(4);

tree.preorder(tree.root);
tree.inorder(tree.root);
tree.postorder(tree.root);