1. 내부 정렬

2. 외부 정렬

1. 차수( Degree ) 가 2 이하인 노드들로만 구성된 트리

이진 트리 운행법( Traversal )

전위 : Root -> Left -> Right

중위 : Left -> Root -> Right

후위 : Left -> Right -> Root

수식의 표기법

전위 표기법 : 연산자 -> 피연산자 -> 피연산자        +AB

중위 표기법 : 피연산자 -> 연산자 -> 피연산자        A+B

후위 표기법 : 피연산자 -> 피연산자 -> 연산자        AB+

ex) (A * B ) + ( C * D ) 중위식을 전위,후위식으로 표기

1. 전위 표기법 : 연산자 우선순위로 ( )를 묶어 준다

1) ( ( A * B ) + ( C * D ) ) :괄호 앞으로 연산자를 빼낸다

2) +( * ( AB ) * ( CD ) ) : 괄호를 제거한다

3) + *AB * CD

2. 후위 표기법 : 연산자 우선순위대로 ( )를 묶어준다

1) ( ( A * B ) + ( C * D ) ) :괄호 뒤로 연산자를 빼낸다

2) ( ( AB ) * ( CD *) + ) : 괄호를 제거

3) AB * CD * +

정의 : 노드(Node)와 가지(Branch)를 이용하여 사이클을 이루지 않도록 구성한 자료 구조

노드( Node ) : 트리의 기본 구성 요소들( a, b, c, d 등등)

근노드( Root Node ) : 가장 상위의 위치한 노드(a)

레벨( Level ) : 근노드를 기준으로 특정 노드까지의 경로 길이( ex) a -> i 까지의 경로길이 )

조상 노드( Ancestors Node ) : 어떤 노드에서 근노드에 이르는 경로상의 모든 노드 

부모 노드( Parent Node ) : 어떤 노드에 연결된 이전 레벨의 노드

자식 노드( Child Node ) : 어떤 노드에 연결된 다음 레벨의 노드

형제 노드( Brother Node ) : 같은 부모를 가진 노드

깊이 ( Depth ) : 트리의 최대 레벨

차수 ( Degree ) : 어떤 노드에 연결된 자식 노드의 수

단말 노드( Terminal Node ) : 트리의 제일 마지막에 위치한 노드( 차수 = 0 )