트리(Tree) (2과목)

트리의 개요

• 트리는 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태이다.
• 하나의 기억공간은 노드, 노드와 노드를 연결하는 선은 링크라고 한다.
• 노드, 근 노드(Root Node), 디그리(Degree, 차수), 단말 노드, 자식 노드, 부모 노드, 형제 노드 등의 개념이 있다.
  • 근 노드는 트리의 맨 위의 기준 노드이다.
  • 차수는 각 노드에서 뻗어나온 가지의 수이다.
  • 단말 노드는 자식이 없는 노드이다. 디그리가 0인 노드
  • 형제 노드는 동일한 부모를 갖는 노드이다.

트리의 운행법

• Preorder 운행, Inoder 운행, Postorder 운행이 있다.
• 각각 Root노드의 순서만 바뀐다.
• Preorder : Root - Left - Right
• Inorder : Left - Root - Right
• Postorder : Left - Right - Root
• 노드의 운행 순서는 자식노드를 크게 묶어버리면 계산하기 쉽다.

수식의 표기법

• 전위, 중위, 후위 표기법이 있는데 이는 연산자의 위치를 바꾼다. 평소에 흔히 사용하는 방식이 중위 표기법이다.
• 전위 표기법(PreFix) : +AB, 연산자 - Left - Right
• 중위 표기법(InFix) : A+B, Left - 연산자 - Right
• 후위 표기법(PostFix) : AB+, Left - Right - 연산자
• 이 또한 묶으면서 계산하면 편하다. 인접한 두개의 노드를 하나의 연산자와 묶어서 생각하자.