[정보올림피아드 대비]21. 트리 활용한 문제

1. 트리의 개념

루트(root)라는 특별한 노드(Node)를 갖고 그래프를 구성하는 꼭짓점 u,v 간에 단순 경로가 존재하는 비순환 연결 그래프를 트리(Tree)라고 한다.

예)

 

오른쪽 트리(Tree) 를 기준으로 개념이해

• 루트(Root)노드 :  트리의 가장 높은 곳에 위치하는 시작 노드인 A
• 부모(Parent)노드 : 트리를 구성하는 임의의 노드의 한단계 상위노드 (예- B,C,D의 부모 노드는 A)
• 자식(Child)노드 : 트리를 구성하는 임의의 노드의 한단계 하위노드(예-B의 자식 노드는 E,F)
• 형제(Sibling)노드 : 트리를 구성하는 임의의 노드와 부모가 같은 노드(예-E의 형제는 F)
• 리프(Leaf)노드 : 트리를 구성하는 임의의 노드중 자식이 없는 노드(예-E,F,C,G)
• 중간(Internal)노드 : 루트노드와 리프노드를 제외한 노드(예-B,D)
• 조상(Ancestor)노드 : 트리를 구성하는 임의의 노드에서 루트노드에 이르는 경로에 포함된 모든 노드(예:E의 조상노드는 B,A)
• 자손(Descendant)노드 : 임의의 한 노드에서 리프노드에 이르는 경로에 포함된 모든 노드(예:B의 자손노드는 E,F)
• 서브(Sub)트리 : 트리인 그래프 T의 임의의 한 노드를 루트로 하는 트리 

• 차수(Degree) : 임의의 한 노드에 포함된 자식 노드의 개수

• 레벨(Level) : 루트노드를 0레벨로 시작하여 자식노드로 한단계씩 내려갈 때마다 한단계씩 증가하는 단계

• 높이(Height)/깊이(Depth) : 트리의 최대레벨(위의 트리는 깊이 2이다.)

 

2. 노드와 모서리에 대한 정리

트리에서 노드의 개수를 v, 모서리의 개수를 e라고 하면 e = v-1이다.

트리구조는 Cycle이 존재 하지 않기 때문에 노드가 하나씩 생길 때 마다 모서리가 하나씩 증가 되는 것을 알 수 있다.

 

3. 이진트리의 개념

이진트리는 트리의 최대 차수가 2인 트리이다.

최대 차수가 2인 이진트리이다.

• 완전이진트리 : 높이가 h일때 0부터 h-2까지의 모든 노드의 차수가 2차이고, 레벨 h-1는 왼쪽부터 노드가 채워져 있는 트리

1레벨은 왼쪽부터 노드가 채워져 있다.

 

• 포화이진트리 : 높이가 h일 때 레벨 0부터 h-1까지의 모든 노드의 차수가 2차인 트리

1레벨까지 모두 2차이다

• 편향이진트리 : 왼쪽이나 오른쪽 서브트리만 가지는 트리

4. 이진트리의 노드 수 정리

• 레벨 k에서 가질 수 있는 최대 노드수 : 2^k개(포화이진 트리에서 레벨 0은 노드수 1개,레벨1은 노드수 2개,레벨 2는 노드수 4 씩 증가 된다.)
• 높이가 k에서 가질 수 있는 최대 노드 수 : 2^k+1 -1 ( 높이 2인 포화이진트리의 갯수는 1+2+4 = 7 이고 2³-1 개이다.)
• 높이가 k에서 가질 수 있는 최소 노드 수 : k+1 (편향이진트리에서 높이 2인 노드의 개수는 3개이다.)

 

5. 이진트리의 순회

• 순회 : 모든 노드의 데이터를 처리 할 수 있도록 한 번씩 방문한다.
  • 항상 루트 노드에서 시작한다.
  • 노드의 데이터를 읽기 전에 노드가 존재하는지 먼저 탐색
  • 형제 노드 중 왼쪽 노드를 항상 먼저 탐색
• 전위순회 : 부모노드-왼쪽자식서브트리방문(서브트리에서 동일하게 왼쪽 자식이 루트가 되어 같은 순으로 방문)-오른쪽자식서브트리방문 순으로 탐색

A-B-D-E-C-F-G 순으로 방문

• 중위순회: 왼쪽자식서브트리방문(서브트리에서 동일하게 왼쪽 자식이 루트가 되어 같은 순으로 방문)-부모트리-오른쪽자식서브트리방문 순으로 탐색

D-B-E-A-F-C-G 순으로 방문

• 후위순회 : 왼쪽자식서브트리방문(서브트리에서 동일하게 왼쪽 자식이 루트가 되어 같은 순으로 방문)-오른쪽자식서브트리방문-부모트리 순으로 탐색

D-E-B-F-G-C-A 순으로 방문

 

 

[역대 기출문제]

docs.google.com/forms/d/e/1FAIpQLSfCzzGqVayTic5zkxhp8muBPzHi0xu7RHvhb9BBolvnTBRlUQ/viewform