자료구조 - Tree 에 관한 이론 문서

소개

자료구조에서 중요한 부분 중에 하나인 트리에 관하여 자세한 이론 설명을 담은 문서입니다.

목차

제5장 트리(Tree)
5.1 트리의 개념
5.2 트리의 용어
5.3 트리의 종류
1) 순서 트리와 비순서 트리
2) 유사 트리와 대등한 트리
3) 이진 트리(binary tree)
4) 엄밀한 이진 트리
5) Knuth 이진 트리
6) 정이진 트리(full binary tree)
7) 전이진 트리(complete binary tree)
8) 사향 이진 트리(skewed binary tree)
5.4 트리의 저장법
1) 연속 배열 저장법
2) 연결 리스트 저장법
3) 일반 트리의 이진 트리로의 변환
5.5 트리의 운행(traversal)
1) 일반 트리 운행법
2) 이진 트리의 운행법
5.6 이진 트리를 이용한 산술식의 표현
1) 폴리시 표기법(polish notation)
2) 산술식의 연산
5.7 스레드 이진 트리
1) 전위 운행한 스레드 이진 트리
2) 중위 운행한 스레드 이진 트리
5.8 경로 길이
1) 내부 경로 길이
2) 외부 경로 길이

본문내용

제5장 트리(Tree)

• 비선형 구조(non-linear structure)
• 나무를 뒤집어 놓은 모양을 하고 있어 트리 구조라 함
• 각 자료 항목간의 계층 관계를 표현하는 자료 구조

5.1 트리의 개념

• 구성 : 노드(node) : 자료를 저장
간선(edge) : 각 노드를 연결시켜 줌
• 그래프(graph)의 특수한 형태
• 어떠한 두 정점 사이에도 사이클(cycle)이 없어야 함
• 두 노드 사이의 경로는 오직 하나만 존재해야함
• 다음 두 조건을 만족하는 한 개 이상의 노드로 구성된 유한 집합
① 최상위 노드를 근(root)노드라 하며 근노드는 1개만 존재한다.
② 근노드를 제외한 나머지 노드들은 n(n≥0)개의 부분 집합인 T1,T2,… Tn으로 분리할 수 있다. 이를 T1, T2,…Tn은 각각 하나의 트리가 되며 근노드의 부트리(subtree)라고 한다.
5.2 트리의 용어

① 노드(node)
? 트리를 구성하는 요소
- 그림 5.1에서 A, B, …, K가 노드

② 근노드(root node)
- 트리에서 레벨이 제일 높은 노드
- 그림 5.1에서 A 노드

③ 부모 노드(parent node)
? 임의의 노드에 연결된 바로 위의 레벨에 있는 노드
- 그림 5.1에서 E의 부모 노드는 B이다.

④ 자식 노드(children node)
? 임의의 노드에 연결된 바로 아래의 레벨에 있는 노드
- 그림 5.1에서 B의 자식 노드는 D와 E이다.

⑤ 형제 노드(sibling node)
? 같은 부모를 갖는 노드
- 그림 5.1에서 B, C와 F, G는 각각 형제 노드

참고자료

· 없음