트리 순회 방식과 수식 표기법 변환

        A
      /   \
     B     C
    / \   / \
   D   E F   G
  / \
 H   I

PREORDER

• preorder 운행법은 이진 트리를 ROOT→ LEFT→ RIGHT 순으로 운행하여 노드들을 찾아가는 방법이다.

서브 트리를 하나의 노드로 생각할 수 있도록 서브 트리 단위별로 묶어 생각하면 된다. 다른 운행법 모두 공통으로 사용한다.

• PREORDER는 ROOT→LEFT→RIGTH이므로 A,B,C순이 된다.
• B는 B→D→E이므로 ABDEC순이 된다.
• D는 D→H→I이므로 ABDHIEC순이 된다.
• C는 C→F→G이므로 ABDHIECFG순이 된다.

A→B→D→H→I→E→C→F→G

• </aside>
• <aside> 💡

INORDER

• INORDER 운행법은 이진 트리를 LEFT→ROOT→RIGHT 순으로 운행하며 노드들을 찾아가는 방법이다.
  • INORDER는 LEFT→ROOT→RIGHT이므로 B→A→C 순이 된다.
  • B는 D→B→E이므로 DBEAC순이 된다.
  • D는 H→D→I이므로 HDIBEAC순이 된다.
  • C는 F→C→G이므로 HDIBEAFCG순이 된다.
  H→D→I→B→E→A→F→C→G

POSTORDER

• POSTORDER 운행법은 이진 트리를 LEFT→RIGHT→ROOT 순으로 운행하며 노드들을 찾아가는 방법이다.
  • POSTORDER는 LEFT→RIGHT→ROOT 이므로 B→C→A가 된다.
  • B는 D→E→B이므로 DEBCA순이 된다.
  • D는 H→I→D이므로 HIDEBCA순이 된다.
  • C는 F→G→C이므로 HIDEBFGCA순이 된다.
  H→I→D→E→B→F→G→C→A

POSTFIX로 표기된 수식을 INFIX로 바꾸기

• POSTFIX는 INFIX 표기법에서 연산자를 해당 피연산자 두개의 뒤로 이동한 것이므로 연산자를 다시 피연산자 두개의 가운데로 옮기면 된다.

ABC-/DEF++→A/ (B-C)+ D(E+F)

• 먼저 인접한 피연산자 두개와 오른쪽의 연산자를 괄호로 묶는다.

((A(BC-)/)(D(EF+)*)+)

• 연산자를 해당 피연산자의 가운데로 이동시킨다.

((A/ (B-C))+(D*(E+F)))

• 필요 없는 괄호를 제거한다.

A/( B-C)+D*(E+F)