트리 순회.md

트리 순회

트리 순회는 트리 자료구조에서 각 노드를 한 번씩 탐색하는 알고리즘을 말합니다. 이 트리 순회는 여러 방법이 있지만 재귀를 이용할 수 있는 순회는 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder)가 있습니다. 모든 순회는 루트 노드부터 시작하며 어떤 노드를 먼저 방문하는지가 달라집니다.

     1
    / \
   /   \
  2     \
 / \     3
4   5   / \
       6   \
            7
           / \
          8   9

전위 순회

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

1, 2, 4, 5, 3, 6, 7, 8, 9

중위 순회

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

4, 2, 5, 1, 6, 3, 8, 7, 9

후위 순회

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

4, 5, 2, 6, 8, 9, 7, 3, 1

소스코드

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

Reference

• www.google.com

---

Back