[C언어로 쉽게 풀어쓴 자료구조] 8장

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

02 다음 트리를 전위 순회로 운행할 경우 다섯 번째로 탐색되는 것은?

03 다음 그림과 같은 이진트리를 후위 순회(postorder traversal)한 결과는?

04 다음 트리에서 단말 노드 수는?

05 다음 그림에서 트리의 차수는?

06 Y=A*B*C/D 를 후위 표기 수식으로 표기하면?

 

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

 

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

(1)완전 이진 트리(complete binary tree)

(2)포화 이진 트리(full binary tree)

(3)스레드 이진 트리(threaded binary tree)

(4)경사 트리(skewed tree)

 

09 배열에 정렬된 값이 들어 있는 경우에 우리는 이진 탐색이라는 효과적인 탐색 기법을 사용할 수 있다. 하지만 배열의 특성상 중간에서 요소를 삽입하거나 삭제하는 것은 비효율적이다. 이진 탐색 트리는 삽입이나 삭제가 비교적 효율적으로 이루어진다. 크기가 n인 이진 탐색 트리에서 다음표를 채워보자.

 

삭제연산알고리즘	평균의 시간복잡도	최악의 시간복잡도
탐색연산	O(logn)	O(n)
삽입연산

10 다음의 이진트리에 대하여 다음 질문에 답하라.

(1)위의 트리를 1차원 배열로 표현하시오.

(2)위의 트리를 전위 순회한 결과를 쓰시오.

(3)위의 트리를 후위 순회한 결과를 쓰시오.

(4)위의 트리를 중위 순회한 결과를 쓰시오.

(5)위의 트리를 레벨 순회한 결과를 쓰시오.

(6)위의 트리는 이진 탐색 트리인가? 그 이유는?

 

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

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

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

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

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

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

(5)생성된 이진탐색트리를 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));
}

 

13 이진 트리의 서브 트리의 높이가 최대 1차이나는 트리를 "균형 트리(balanced tree)"라고 한다. 주어진 이진 트리가 균형 트리인지를 검사하는 함수 isBalanced()를 작성하고 테스트하라.

 

14 주어진 이진트리에서 노드가 가지고 있는 값의 합을 계산하는 프로그램을 작성해보자.

노드의 합은 129입니다.

15 주어진 이진트리에서 노드가 가지고 있는 값이 주어진 value보다 작으면 노드의 값을 출력하는 프로그램을 작성해보자.

값을 입력하시오: 30
30보다 작은 노드: 10
30보다 작은 노드: 9
30보다 작은 노드: 29
...

16 주어진 이진 트리에서 자식이 하나만 있는 노드의 개수를 반환하는 함수를 작성하라.

 

17 일반 이진 트리에서 최대값과 최소값을 탐색하기 위한 함수를 작성하라. 이진 탐색 트리가 아니다.

hint 순환호출을 사용하라

최소값=1
최대값=120

18 숫자들이 들어 있는 이진 탐색 트리를 중위 순회하면 정렬된 숫자가 얻어진다. 이를 이용하여 다음 배열에 들어 있는 숫자들을 정렬시키는 함수를 작성하여 보라. 배열에 들어 있는 숫자들을 이진 탐색 트리에 추가한 후에 트리를 중위 순회하면서 숫자들을 출력한다. 단 숫자들은 중복되지 않는다고 가정하자.

0                        1                 2                  3                 4                      5                6                   7                   8              9         10

11

3

4

1

56

5

6

2

98

32

23

 19 18번은 오름차순으로 정렬시키는 경우이다. 이진 탐색 트리를 이용하여 배열에 저장된 숫자들을 내림차순으로 정렬시키는 함수를 작성하려 보라.

 

20 이진 탐색 트리의 모든 노드의 값을 1씩 증가시키는 함수를 작성하여 보라.

 

21 이진 탐색 트리를 사용하여 우선순위 큐를 구현할 수도 있다. 우선순위 큐란 항목들이 우선순위를 가지고 있고 우선순위가 가장 큰 항목이 먼저 삭제되는 큐이다. 이진 탐색 트리에서 가장 큰 값을 찾으려면 어떻게 해야 하는가?

 

22 이진 탐색 트리의 가장 큰 용도가 map(사전)이라는 자료구조를 구현하는 것이다. 본문에서 우리는 단어장을 구현해보았다. 여기서는 이진 탐색 트리를 이용하여 친구들의 연락처를 저장하고 탐색하는 프로그램을 작성해보자.

 

삽입(i), 탐색(s), 삭제(d) : i
친구의 이름: 홍길동
친구의 전화번호: 010-1234-5678
삽입(i), 탐색(s), 삭제(d) : i
친구의 이름: 김철수
친구의 전화번호: 010-1234-5679
삽입(i), 탐색(s), 삭제(d) : s
친구의 이름: 김철수
친구의 전화번호: 010-1234-5679
...