07.트리

목차

없음

본문내용

2. 다음에서 트리 구조로 나타내기에 적합하지 않은 것은?

(2) 행렬
: 트리 구조는 계층적인 자료를 표현하는 데 적합한 자료 구조이다.행렬은 선형 리스트와 같이 자료들이 직선과 같이 나열되어 있는 구조에 더 적합하다.

4. 이진 트리를 설명한 내용 중 잘못된 것은?

(3) 일반적인 이진 트리는 배열로 저장시킬 수 없다.
: 포화 이진 트리나 완전 이진 트리 뿐만 아니라 그 외의 일반적인 이진 트리도 배열로 저장할 수 있다.배열로 표현할 경우 인덱스만 알고 있으면 노드의 부모나 자식을 쉽게 알 수 있는 반면에,기억 공간의 낭비가 심하다는 단점이 있다.

6. 메모리상에 배열로 저장할 때 가장 낭비가 큰 트리는?

(1) 경사 트리
: 우선 배열로 저장할 때는 트리가 완전 이진 트리라고 가정하고 번호대로 노드를 저장한다.경사 트리의 경우 한 레벨에 하나의 노드가 존재하기 때문에 채워지지 않는 공간이 많이 생기므로 낭비가 가장 심한 트리라고 할 수 있다.

8.트리를 포인터를 이용하여 표현할 경우,각 노드가 가져야 할 포인터의 수는?

(1) 트리의 차수 만큼
: 포인터를 이용하여 트리를 표현할 경우, 각 노드는 자신이 가지고 있는 자식 노드와 각각 연결되어야 한다.따라서 각 노드가 가지고 있는 자식 노드의 개수만큼 포인터가 필요하기 때문에 결국 트리의 차수 만큼의 포인터가 필요하다.

12. 다음 문장들이 맞는지 틀린지를 말하고 만약 틀린 문장이면 맞게 고쳐라.

(1) 트리는 선형(->비선형) 자료 구조의 일종이다. (X)
(2) 공집합도 이진 트리에 속한다. (O)
(3) 다음의 이진 트리는 동일하다(-> 동일하지 않다.). (X)
(4) 모든 포화 이진 트리는 완전 이진 트리이다.(O)
(5) 높이가 3인 이진 트리에 존재할 수 있는 최대 노드의 개수는 8개(->7개) 이다. (X)
(6) 배열 표현법은 완전 이진 트리의 경우,공간의 낭비가 심하다. (X)
:완전 이진 트리의 경우 공간의 낭비가 거의 없고, 경사 트리를 배열로 표현할 경우 공간의 낭비가 심하다.

참고 자료

없음