[DFS]이진트리 순회

문제

아래 그림과 같은 이진트리를 전위순회, 중위순회, 후위순회를 돈 결과를 출력하세요.

개념

트리(Tree)

• 노드(node)로 이루어진 비선형 자료 구조
• 트리는 하나의 루트(root) 노드를 갖고 있음
• 루트 노드는 0개 이상의 자식 노드를 갖고 있음
• 그 자식 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의
• 노드와 노드를 연결하는 간선(edge)들로 구성

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가짐
• 단말 노드(leaf node): 자식이 없는 노드, '말단 노드' 또는 '잎 노드' 라고도 불림
• 내부 노드(internal node): 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선(link, branch 라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수: 각 노드가 지닌 가지의 개수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

---

이진 트리(Binary Tree)

• 각 노드가 최대 두 개의 자식을 갖는 트리
• 모든 트리가 이진 트리는 아님

이진 트리 순회

• 전위 순회(pre-order-traversal): 현재 노드 => 왼쪽 노드 => 오른쪽 노드
• 중위 순회(in-order-traversal): 왼쪽 노드 => 현재 노드 => 오른쪽 노드
• 후위 순회(post-order-traversal): 왼쪽 노드 => 오른쪽 노드 => 현재 노드

이진 탐색 트리(Binary Search Tree)

• 모든 왼쪽 자식들 <= N <= 모든 오른쪽 자식들

완전 이진 트리(Complete Binary Tree)

• 트리의 모든 높이에서 노드가 꽉 차 있는 트리
• 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함

문제풀이

1. 현재 트리는 부모 노드(x) 기준 왼쪽 노드의 값은 x*2 오른쪽 노드의 값이 x*2+1 로 이루어져 있다.
2. 해당 문제에서는 별도로 트리 자료구조가 필요한 것이 아닌 순서도만을 산출해내면 되기 때문에 재귀 함수와 스택 프레임을 사용한다.
3. 아래 그림의 호출 순서를 중점으로 중간 연산자를 어디에 배치하냐에 따라 순회를 달리 산출한다.

 

코드

function solution(n){
  let answer="";
  function DFS(v){
      if(v>7) return;
      else{
          DFS(v*2);
          answer+=(v+' ');
          DFS(v*2+1);
      }
  }
  DFS(n);
  return answer;
}

console.log(solution(1));