이진 트리 순회

이진 트리 순회

이진 트리의 데이터를 가져오는 방법에는 다음과 같이 크게 3가지가 있습니다.

• 중위 순회(Inorder)
• 전위 순회(Preorder)
• 후위 순회(Postorder)

중위 순회

중위 순회는 트리를 순회할 때 다음과 같은 방식으로 순회하는 것을 의미합니다.

1. Left child
2. Root (자기 자신을 의미)
3. Right child

코드를 짠다고 하면 다음과 같이 됩니다.

function inorder(node){
  if(node !== null){
    inorder(node.left);
    console.log(node.value);
    inorder(node.right);
  }
}

재귀로 구현이 되고, 코드를 보면 왼쪽 노드가 있는 경우 계속해서 내려가게 됩니다.

전위 순회

전위 순회는 다음과 같은 방식으로 트리를 순회합니다.

1. Root (자기 자신을 의미)
2. Left child
3. Right child

코드를 짠다고 하면 다음과 같이 됩니다.

function preorder(node){
  if(node !== null){
    console.log(node.value);
    preorder(node.left);
    preorder(node.right);
  }
}

재귀를 돌기 전에 자기 자신을 먼저 출력하는 모습을 볼 수 있습니다.

후위 순회

후위 순회는 다음과 같은 방식으로 순회하게 됩니다.

1. Left child
2. Right child
3. Root (자기 자신을 의미)

function postorder(node){
  if(node !== null){
    postorder(node.left);
    postorder(node.right);
    console.log(node.value);
  }
}

후위 순회는 자기 자신 데이터를 출력하는 것이 가장 마지막이 됩니다.