Tree(트리)

Tree

트리는 정점과 선분을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태이다.

트리는 하나의 기억 공간을 노드라고 하며 노드와 노드를 연결하는 선을 링크라고 한다.

트리는 가족의 계복, 조직도 등을 표현하기에 적합하다.

 

Tree 관련 용어

- 노드(Node) : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것

- 근 노드(Root Node) : 트리의 맨 위에 있는 노드

- 디그리(Degree, 차수) : 각 노드에서 뻗어 나온 가지의 수

- 단말 노드(Terminal Node) = 잎노드(Leaf Node) : 자식이 하나도 없는 노드, 즉 디그리가 0인 노드

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

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

- 형제 노드(Brother Node, Sibling) : 동일한 부모를 갖는 노드들

- 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수

Tree의 운행법

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

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

- 전위순회(Preorder Traversal) : Root -> Left -> Right 순으로 운행한다.

- 중위순회(Inorder Traversal) : Left -> Root-> Right 순으로 운행한다.

- 후위순회(Postorder Traversal): Left -> Right -> Root 순으로 운행한다.

- 알고리즘 BFS, DFS과 관련되어 있으니 꼭 기억하자

 

수식의 표기법

산술식을 계산하기 위해 기억공간에 기억시키는 방법으로 이진 트리를 많이 사용한다. 

이진 트리로 만들어진 수식을 인오더, 프리오더, 포스트오더로 운행하면 각각 중위(Infix), 전위(Prefix), 후위(Postfix) 표기법이 된다.

 

- 전위 표기법(PreFix) : 연산자 -> Left -> Right, +AB

- 중위 표기법(InFix) : Left -> 연산자 -> Right, A+B

- 후위 표기법(PostFix) : Left -> Right -> 연산자, AB+

 

Infix -> PreFix, PostFix 변환할 때 순서

1. 연산 순서에 따라 괄호 

2. PreFix면 연산자를 앞으로, PostFix면 연산자를 뒤로 이동

3. 필요없는 괄호 제거

 

Infix -> PreFix

Infix값     X = A / B * ( C + D ) + E

1. ( X = ( ( ( A / B ) * ) ( C + D ) + E ) )

2. = ( X + ( * ( / ( A B ) + ( C D ) ) E ) )

3. = X + * / A B + C D E

 

Infix -> PostFix

Infix값     X = A / B * ( C + D ) + E

1. ( X = ( ( ( A / B ) * ) ( C + D ) + E ) )

2. ( X ( ( A B ) / C D ) + ) * E ) + ) =

3. X A B / C D + * E + =

 

코드로 짜봐야함 수정중