트리/이진트리

트리(Tree)

① 1:N 또는 1:1 대응 구조로 노드(Node, 정점)와 선분(Branch)으로 되어 있고, 정점 사이에 사이클이 형성되어 있지 않음

② 자료 사이의 관계성이 계층 형식으로 나타나는 구조

③ 노드 사이의 연결 관계가 계급적인 구조로 뻗어나간 정점들이 다른 정점들과 연결되지 않는다(1:N 또는 1:1 대응 구조)

 

 

트리 운행법

전위 운행, 중위 운행, 후위 운행의 기준은 근노드의 위치이다.

① 전위 운행 (Root-Left-Right) : ABDHIECFG

② 중위 운행 (Left-Root-Right) : HDIBEAFCG

③ 후위 운행 (Left-Right-Root) : HIDEBFGCA

 

 

 

 

수식의 표기법

① 전위식 : 연산자(+, -, *, /)가 맨 앞에 놓인다(연사자 - 피연산자 - 피연산자)  ex) +AB

② 중위식 : 연산자가 피연산자가 중간에 놓인다(피연산자 - 연산자 - 피연산자)  ex) A+B

③ 후위식 : 연산자가 맨 뒤에 놓인다(피연산자 - 피연산자 - 연산자)  ex) AB+