알고리즘트리_01

소개

알고리즘트리의 정의 및 조건과 이진트리의 성질과 구현을 설명했다. 그리고 트리를 어떤방식으로 응용할 것인가에 대한 결론으로 마무리한다.

목차

서론
Ⅰ. 트리의 정의
Ⅱ. 트리의 조건
Ⅲ. 트리의 용어 설명

본론
Ⅳ. 트리의 종류
1. 자유 트리
2. 순서 트리와 비순서 트리
3. 닮은 트리와 대등트리
4. 이진 트리
1) 이진 트리 정의
2) 이진 트리의 종류
① 스퀴드 트리
② 완전 이진 트리
③ 포화 이진 트리
④ knuth 이진 트리
⑤ 엄밀한 이진 트리
3) 이진 트리의 성질
4) 이진 트리의 표현, 저장 방법
① 배열을 이용한 표현
② 연결 리스트를 이용한 표현
5) 이진 트리의 구현

결론
Ⅴ. 트리의 응용

본문내용

Ⅰ. 트리의 정의

-트리(tree)는 비선형 자료구조 중에서 자료들간에 계층관계를 가진 계층형 자료구조다. 흔히 우리가 알고있는 가계도가 바로 계층형 자료구조이다. 가계도에서 가족 구성원을 연결하는 선은 부보 자식 관계를 나타낸다. 가계도의 시작을 루트로 보고, 그 아래 자식노드는 1세대(레벨1)그 아래의 자식노드들은 2세대(레벨 2) 라고 볼 수 있다. 트리를 구성하는 원소는 노드라고 하고 노드를 연결하는 선을 간선(edge)이라고 한다. 같은 부모 노드의 자식 노드들은 서로 형제 노드가 된다. 한 노드에서 간선을 따라 루트 노드까지 이르는 경로에 있는 노드들은 모두 그 노드의 조상 노드가 된다. 자식 노드들은 각각 독립하여 새로운 트리를 구성할 수 있으므로 각 노드의 자식 노드 수만큼의 서브 트리를 갖는다. 한 노드의 자손 노드들은 그 노드의 서브 트리에 있는 노드들이 된다. 한 노드가 가지는 서브 트리의 수, 즉 자식 노드의 수를 그 노드의 차수라 한다. 한 노드의 높이는 루트에서 그 노드에 이르는 경로에 있는 간선의 수가 되고, 노드의 높이 중에서 가장 큰 값, 즉 최대 레벨이 그 트리의 높이가 된다. 나무가 모이면 숲이 되듯이 여러 트리들의 집합을 포레스트 라고 한다. n개의 서브트리를 가진 루트 노드를 제거하면 n개의 분리된 트리가 생겨서 포레스트를 이룬다.

<중 략>

② 연결 리스트를 이용한 표현
- 연결 리스트를 이용하면 포인터를 이용하여 자신의 왼쪽 자식 노드와 오른쪽 자식 노드를 직접 연결할 수 있다. 일반트리를 연속 배열 저장법으로 저장할 경우 노드의 삽입과 삭제가 곤란하다는 문제점이 있으므로 일반 트리를 링크저장법으로 저장할 경우 이러한 문제점을 해결할 수 있는 장점이 있다. 연결 리스트를 이용하면 배열을 이용하는 경우보다 기억장소의 낭비가 덜하다. 그러나 연결 리스트를 이용하여 저장하기 때문에 각각의 노드는 트리를 구성하는 각 노드의 차수 개수만큼 링크가 필요하고, 노드 내에서 사용하지 않은 널 링크(null link)에 의해 기억공간의 낭비를 초래한다.

참고자료

· 없음