다음과 같은 수식을 이진트리(binary tree)로 표현하였을 때 완… | [9급 서울시 컴퓨터일반] 14년 1회차 기출문제 상세 페이지
1[9급 서울시 컴퓨터일반] 14년 1회차
다음과 같은 수식을 이진트리(binary tree)로 표현하였을 때 완성된 이진트리의 깊이(depth)는 얼마인가? (단, 근 노드(root node)만 존재하는 이진트리의 깊이는 1이다.)((a+b)+c)+d
1
1
2
2
3
3
4
4
5
5
해설
수식 ((a+b)+c)+d를 이진트리로 표현하면 깊이는 4이다.
가장 마지막에 계산되는 연산자가 루트가 되므로 트리는 다음과 같이 왼쪽으로 내려간다.
- 깊이 1: 루트 +(왼쪽은 (a+b)+c, 오른쪽은 d)
- 깊이 2: +(왼쪽은 a+b, 오른쪽은 c)와 d
- 깊이 3: +(왼쪽 a, 오른쪽 b)와 c
- 깊이 4: 단말 노드 a, b
루트만 있을 때 깊이를 1로 정의했으므로 가장 깊은 단말 a, b까지 네 단계가 된다.
오류나 개정된 내용이 보이면 알려주세요