비선형 구조

트리(Tree)

트리의 정의

• 그래프(Graph)의 특수한 형태로써 노드(Node)와 가지(Branch)를 이용하여 사이클을 이루지 않도록 구성한 자료 구조

트리 관련 용어

노드(Node)	트리의 기본 구성 요소	노드(Node)	트리의 기본 구성 요소
근노드(Root Node)	가장 상위에 위치한 노드	레벨(Level)	근노드를 기준으로 특정 노드까지의 경로 길이
조상 노드(Ancestors Node)	어떤 노드에서 근노드에 이르는 경로상의 모든 노드	부모 노드(Parent Node)	어떤 노드에 연결된 이전 레벨의 노드
자식 노드(Child Node)	어떤 노드에 연결된 다음 레벨의 노드	형제 노드(Brother Node)	같은 부모를 가진 노드
깊이(Depth)	트리의 최대 레벨	차수(Degree)	어떤 노드에 연결된 자식 노드의 수
단말 노드(Terminal Node)	트리의 제일 마지막에 위치한 노드(차수=0)	트리의 차수(Degree)	트리의 노드 중 가장 큰 차수

이진 트리(Binary Tree)

• 차수(Degree)가 2 이하인 도드들로만 구성된 트리
• 이진 트리의 레벨 K에서 최대 노드의 수 : 2^K - 1
• 깊이(레벨)가 5인 이진 트리의 최대 노드 수는 2^5 - 1이므로 31임

이진 트리의 구조

정이진 트리 (Full Binary Tree)		첫 번째 레벨부터 마지막 레벨까지 모두 2개씩 노드가 채워진 트리
완전 이진 트리 (Complete Binary Tree)		정이진 트리에서 마지막 레벨에서 왼쪽부터 단말 노드를 채우는 트리
사향 이진 트리 (Skewed Binary Tree)		근노드로부터 한쪽 방향으로만 기울어진 트리

수식의 표기법

전위(Prefix) 표기법	연산자 → 피연산자 → 피연산자	+ A B
중위(Infix) 표기법	피연산자 → 연산자 → 피연산자	A + B
후위(Postfix) 표기법	피연산자 → 피연산자 → 연산자	A B +

 

그래프(Graph)

그래프(Graph)

• 정점(Vertex)과 간선(Edge)의 집합으로 이루어지는 자료 구조
• 표현 방법 : 인접 행렬(Adjacency Matrix)
• 신장 트리(Spanning Tree) : 간선들이 사이클을 이루지 않도록 정점들을 연결시킨 그래프
• 종류 : 방향 그래프, 무방향 그래프, 완전 그래프, 부 그래프
• n개의 노드로 구성된 무방향 그래프의 최대 간선 수는 n(n-1)/2개임
• 제어 흐름 그래프에서 순환 복잡도
  • V(G) = E(화살표 수) - N(노드 수) + 2

인접 행렬(Adjacency Matrix)

• 방향 그래프에서 V_1V_2 관계를 나타내는 행렬의 원소를 A_ij라고 할 때, 방향 간선이 있으면 행렬의 A_ij = 1, 방향 간선이 없으면 행렬의 A_ij = 0으로 나타냄
• 무방향 그래프에서 V_i와 V_j가 서로 인접하면 A_ij = 1, 서로 인접하지 않으면 A_ij = 0으로 나타냄