037 트리 - 1장 데이터 입출력 - 2과목 소프트웨어 개발

1. 트리의 개요
   
   1. 정점(node)과 선분(branch)을 이용하여 사이클을 이루지 않도록 구성한 그래프
   2. 노드 →하나의 기억 공간
   3. 링크 → 노드와 노드를 연결하는 선
   4. 가족 계보, 조직도 등에 적합
   5. 근 노드(root node) → 맨 위에 있는 노드
   6. 디그리 → 각 노드에서 뻗어 나온 가지의 수
   7. 단만 노드(Terminal Node) = 잎 노드(Leaf Node) → 자식이 하나도 없는 노드 = 디그리 0
   8. 자식 노드 → 어떤 노드에 연결된 다음 레벨의 노드들
   9. 부모 노드 → 어떤 노드에 연결된 이전 레벨의 노드들
   10. 형제 노드 → 동일한 부모를 갖는 노드들
   11. 트리의 디그리 → 디그리 중 가장 많은 수
2. 트리의 운행법
   1. 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다
   2. 세가지 운행법
      1. 운행법 이름은 root의 위치가 어디 있느냐에 따라 정해진다
      2. Preorder : Root → Left → Right
      3. Inorder : Left → Root → Right
      4. Postorder : Left → Right → Root
3. 수식의 표기법
   1. 산술식을 계산하기 위해 기억공간에 기억시키는 방법으로 이진 트리를 많이 사용한다
   2. 인오더, 프리오더, 포스트오더로 운행하면 각각 중위(Infix), 전위(Prefix), 후위(Postfix) 표기법이 된다
      1. 전위 표기법 : 연산자 → left → right, +AB
      2. 중위 표기법 : left → 연산자 → right, A+B
      3. 후위 표기법 : left → right → 연산자, AB+
      4. infix → postfix or prefix로 바꾸기
         1. postfix or prefix는 스택을 이용하여 처리하므로 infix는 postfix나 prefix로 바꾸어 처리
            1. 예) X = A / B * (C + D) + E
               1. prefix
               2. 연산 우선순위에 따라 괄호로 묶는다. ( X = (((A / B) * (C + D)) + E))
               3. 연산자를 해당 괄호의 앞(왼쪽)으로 옮긴다. = (X +(*(/(AB)+(CD))E))
               4. 필요없는 괄호를 제거한다 prefix 표기 : = X + * / AB + CDE
               5. porstfix 1.연산 우선순위에 따라 괄호로 묶는다. ( X=((A / B) * (C + D)) + E ))
               2.연산자를 해당 괄호의 뒤(오른쪽)으로 옮긴다. ( X ( ( A B ) / ( C D ) + ) * E ) + ) =
            2. 3.필요없는 괄호를 제거한다 Postfix 표기 : X A B / C D + * E + =
         2. postfix → infix
            1. 예) A B C - / D E F + * +
            2. postfix는 연산자를 해당 피연산자 두 개의 뒤로 이동한 것이르모 연산자를 다시 가운데로 옮긴다.
            3. 먼저 인접한 피연산자 두 개와 오른쪽의 연산자를 괄호로 묶는다. ( ( A / ( B - C ) ) + ( D * ( E + F ) ) )
            2.연산자를 해당 피연산자의 가운데로 이동시킨다. ( ( A / ( B - C ) ) + ( D * E + F ) )
         3. 3.필요 없는 괄호를 제거한다. A / ( B - C ) + D * ( E + F )
         4. prefix → infix
            1. 예) + / A - B C * D + E F
            2. prefix는 연산자를 해당 피연산자 두 개의 앞으로 이동한것이므로 연산자를 다시 해당 가운데로 옮긴다.
            3. 먼저 인접한 피연산자 두 개와 왼쪽의 연산자를 괄호로 묶는다. ( + ( / A ( - B C ) ) ( * D ( + E F ) ) )
            2.연산자를 해당 피연산자 사이로 이동시킨다. ( ( A / ( B - C ) ) + ( D * ( E + F ) ) )
         5. 3.필요 없는 괄호를 제거한다. A / ( B - C ) + D * ( E + F )