[자료구조] 10주차 과제

1번 다음 트리에 대한 중위 순회 결과는?

 

1) A B D C E F

2) A B C D E F

3) D B E C F A

4) D B A E C F

 

답: 4) D B A E C F

풀이: 중위 순회는 우선순위가 다음과 같다.

왼쪽 서브 트리 순회 -> 노드 방문 -> 오른쪽 서브 트리 순회.

 

3번 다음 그림과 같은 이진 트리를 후위 순회한 결과는?

1) + * * / A B C D E

2) A / B * C * D + E

3) + * A B / * C D E

4) A B / C * D * E +

 

답: 4) A B / C * D * E +

풀이: 후위 순회는 우선순위가 다음과 같다.

왼쪽 서브 트리 순회 -> 오른쪽 서브 트리 순회 -> 노드 방문.

이전 챕터에서 학습한 후위표기식이라고 생각된다.

 

7번 이진 트리에서 높이가 5일 때, 이 트리는 최대 몇 개의 노드를 가질 수 있는가?

1) 26개             2) 8개              3)32개              4)31개

 

답: 4) 31개

풀이: 2^5 – 1 = 32 -1 = 31

높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며 최대 2^h -1개의 노드를 가진다.

이유는 한 레벨에는 적어도 하나의 노드는 존재해야 하므로 높이가 h인 이진 트리는 적어도 h개의 노드를 가진다. 또한 하나의 노드는 최대 2개의 자식을 가질 수 있으므로 레벨 i에서의 노드의 최대 개수는 2^(i-1)이 된다. 따라서 전체 노드 개수는 2^h -1이 된다.

 

 

 

8번 NULL 포인터를 트리의 순회에 이용하는 트리를 무엇이라 하는가?

1) 완전 이진 트리

2) 포화 이진 트리

3) 스레드 이진 트리

4) 경사 트리

 

답: 3) 스레드 이진 트리

풀이: 이진 트리 순회는 순환 호출을 사용한다. 순환 호출은 함수를 호출해야 되므로 상당히 비효율적일 수가 있다. 이진 트리 순회도 노드의 개수가 많아지고 트리의 높이가 커지게 되면 상당히 비효율적일 수도 있다. NULL 링크를 잘 사용하여 순환호출 없이도 트리의 노드를 순회할 수 있도록 하자는 의견에서 나온 것이 중위 선행자나 중위 순회시에 후속 노드인 중위 후속자를 저장시켜 놓은 트리가 스레드 이진 트리이다.

 

 

 

11번 다음 순서로 자료가 입력되었다고 가정하여 이진 탐색 트리를 생성하라.

11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31

 

(1) 생성된 이진탐색트리를 그리시오.

 

풀이: 이진 탐색 트리의 성질

1. 모든 원소의 키는 유일한 키를 가진다.

2. 왼쪽 서브 트리 키들은 루트 키보다 작다.

3. 오른쪽 서브 트리 키들은 루트의 키보다 크다.

4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

(2) 여기서 11를 삭제하면 어떻게 변경되는가?

 

풀이: 삭제 연산은 3가지 경우가 있는데 그 중 이것은 삭제하려는 노드가 2개의 서브 트리를 가지고 있는 경우이다. 이런 경우 왼쪽 서브 트리에서 제일 큰 값 혹은 오른쪽 서브 트리에서 제일 작은 값을 넣어 주어야한다. 후계자 대상 노드는 10과 17이다.

 

(3) 여기에 12를 추가하면 어떻게 변경되는가?

 

풀이: 삽입 연산은 이진 탐색 트리의 성질을 잘 생각해보면 된다. 좌측은 루트보다 작은 값, 우측은 루트보다 큰 값이 들어 간다는 점을 생각해보면 12는 17의 왼쪽 자식 노드가 되면 된다.

 

(4) 생성된 이진탐색트리에서 8을 탐색할 때 거치는 노드들을 나열하시오.

 

답: 11 -> 6 -> 8

풀이: 루트 노드를 시작으로 11 > 8 이므로 left. 6 < 8 이므로 right.

11 -> 6 -> 8의 순서로 8을 탐색할 수 있다.

 

(5) 생성된 이진탐색트리를 1차원 배열을 이용하여 저장하여 보시오. 저장된 결과를 그리시오.

 

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
사용 X	11	6	19	4	8	17	43				10			31	49

풀이: 배열 표현법시 인덱스 0은 사용하지 않음. 높이가 4이므로 2^4 -1 개의 공간을 연속적으로 할당한 다음, 완전 이진 트리의 번호대로 노드들을 저장한다. 완전 이진 트리가 아닌 일반적인 이진 트리인 경우에는 다음과 같이 기억공간의 낭비가 심해진다.

 

 

12번 다음과 같은 함수가 아래에 표시된 이진 트리의 루트 노드에 대해 호출된다고 하자. 함수가 반환하는 값은 무엇인가?

 

int mystery (TreeNode* P)

{

           if (p == NULL)

return 0;

           else if (p->left == NULL && p->right == NULL)

return p->data;

           else

                     return max(mystery(p->left), mystery(p->right));

           }

 

답: 8

풀이: max() 함수는 두개의 인자 중 더 큰 수를 반환한다. 그러므로 p->left 와 p-> right가 모두 NULL이 되는 단말 노드 중 가장 큰 값인 8이 반환한다.