[정처기] 데이터 입출력 구현_이진 트리

이진 트리

차수가 2 이하인 노드들로 구성된 트리

레벨 i에서 최대 노드의 수는 2^(i-1)

이진 트리에서 리프 노드의 개수가 n_0, 차수가 2인 노드 수가 n_2라 할 때, n_0 = n_2 + 1

트리의 운행법

트리를 구성하는 각 노드들을 찾아가는 방법을 운행법이라 한다

이진트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다

• Proorder : Root > Left > Right
• Inorder : Left > Root > Right
• Postorder : Left > Right > Root

수식의 표기법

• 전위 표기법 : 연산자 > Left > Right
• 중위 표기법 : Left > 연산자 > Right
• 후위 표기법 : Left > Right > 연산자

Infix 표기를 Postfix나 Prefix로 바꾸기

예제) X = A/B*(C+D)+E

• Prefix로 변환
  1. 연산 우선순위에 따라 괄호로 묶기
     (X=(((A/B)*(C+D))+E))
  2. 연산자를 해당 괄호의 앞(왼쪽)으로 옮긴다
     = (X + ( * ( / (AB) + (CD))E))
  3. 괄호 제거
     = X+* / AB + CDE
• Postfix로 변환
  1. 연산 우선순위에 따라 괄호로 묶기
     (X=(((A/B)*(C+D))+E))
  2. 연산자를 해당 괄호의 뒤(오른쪽)로 옮긴다
     (X(((AB) / (CD) + * )E) + ) =
  3. 괄호 제거
     XAB / CD + * E + =
     

Postfix나 Prefix로 표기된 수식을 Infix로 바꾸기

예제) ABC-/DEF+*+

• Postfix > Infix
  1. 먼저 인접한 피연산자 두 개와 오른쪽의 연산자를 괄호로 묶는다
     ((A(BC-)/)(D(EF+)*)+)
  2. 연산자를 해당 피연산자의 가운데로 이동시킨다
     ((A / (B - C)) + (D * (E + F)))
  3. 필요없는 괄호 제거
     A / (B - C) + D * (E + F)

예제) +/A-BC*D+EF

• Prefix > Infix
  
  1. 먼저 인접한 피연산자 두 개와 왼쪽의 연산자를 괄호로 묶는다
     (+(/A(-BC))(*D(+EF)))
  2. 연산자를 해당 피연산자 사이로 이동시킨다
     ((A / (B - C)) + (D * (E + F)))
     
  3. 필요없는  괄호 제거
     A / (B - C) + D * (E + F)