c언어로 쉽게 풀어쓴 자료구조 개정 3판 8장(트리) 연습문제 (해설 포함)

소개

"c언어로 쉽게 풀어쓴 자료구조 개정 3판 8장(트리-1) 연습문제 (해설 포함)"에 대한 내용입니다. 답만 올린게 아니라 독자분들이 이해할 수 있도록 각 문제마다 풀이 과정을 기재했습니다.

목차

없음

본문내용

1. 답) (4)
풀이) 중위 순회는 모든 노드에 대해서 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드 순서대로 순회한다.

2. 답) (2)
풀이) (2)번의 트리를 전위 순회할 경우 A -> B -> D -> C -> E -> G -> H -> F 순으로 순회한다. (모든 노드에 대해서 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드)
따라서 5번째로 탐색되는 노드는 ‘E’ 노드이다.

3. 답) (4)
풀이) 후위 순회는 모든 노드에 대해서 왼쪽 노드 -> 오른쪽 노드 -> 현재 노드 순서대로 순회한다. 따라서 답은 (4)번이다. (*후위 순회에서 루트 노드는 가장 마지막으로 탐색된다.)

4. 답) (3)
풀이) 단말 노드는 자식 노드가 없는 노드를 말한다. 자식 노드가 하나라도 있는 노드는 단말노드가 아니다. 따라서 (4)번 문제의 트리에서 단말 노드는 ‘D’, ‘G’, ‘H’, ‘F’ 총 4개다.

5. 답) (1)
풀이) 트리의 차수는 해당 트리의 모든 노드 중에서 가장 큰 차수를 가진 노드의 차수를 말한다. 노드 ‘B’는 자식 노드가 3개를 가지므로 차수가 3개이다. 이 트리에서 가장 큰 차수를 가지는 노드는 ‘B’이므로 트리의 차수는 ‘B’노드의 차수인 3이다.

6. 답) (3)
풀이) 문제에서 주어진 식은 가장 일반적으로 사용되는 중위 표기식이다. 중위 표기식을 전위표기식으로 바꿔야 하는데, 연산자의 우선순위대로 괄호로 묶어야 한다.
Y = A*B + C/D -> Y = ((A*B) + (C/D))
괄호로 묶은 후 연산자를 자신의 짝인 괄호 앞에 놓는다.
-> Y = +(*(AB)/CD))
괄호를 빼면 Y = +*AB/CD이므로 답은 (4)번이다.
이를 트리로 표현해보자.

이 트리를 전위 순회하면 전위 표기식, 중위 순회하면 중위 표기식, 후위 순회하면 후위 표기식을 나타낸다. 참고로 중위 표기식 <-> 후위 표기식은 스택을 활용해서 계산할 수 있다.

참고자료

· 없음