데이터구조-트리 실습문제

아래 트리T 를 이용하여 문제1~7까지를 푸시오.

문제1

트리T에서 B의 모든 자식노드를 쓰시오.

D,E,F

문제2

서브트리B에 있는 외부노드를 모두 쓰시오.

외부노드란? 자식이 없는 노드

D,F,I,J

 

 

문제3

노드 G의 높이(height)를 쓰시오.

노드의 높이 (Height)

특정 노드에서 가장 멀리 있는 리프(자식이 없는 노드)까지의 거리

제일 끝에 있는 리프  노드가 0 높이부터 시작하므로 

G의 높이는 1

 

문제4

노드 F의 level을 쓰시오.

루트노드 = 레벨 0 부터 아래로 내려갈수록 레벨이 올라가므로

노드 F 의 레벨은 2

문제5

노드 E의 차수를 쓰시오.

차수(degree)

노드가 갖는 자식의 수

2

문제6

노드 G의 모든 조상노드들을 쓰시오.

조상(ancestor)노드

어떤 노드에서 위쪽으로 간선을 따라가면서 만나는 모든 노드

 

C,A

 

문제7

노드 E의 모든 형제노드들을 쓰시오.

형제

같은 부모를 가지는 노드들을  형제라고 한다.

 D,F

 

문제8

O,X 문제

아래 트리는 완전이진트리이다.

 O

완전 이진트리(complete binary tree)

마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고 , 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 이진트리

 

배열을 이용하여 완전이진트리 구현

문제9

배열을 이용한 완전이진트리에서 부모 노드의 키를 리턴하는 함수를 작성하시오.

• 파라미터:
  • complete_binary_tree: 리스트
  • index: 인덱스
• 리턴:
  • index에 위치한 노드의 부모노드의 키 리턴

결과

None
A
B
E

인덱스 값이 리스트 안에 있을때-> if 문으로 범위를 설정하고

범위인 리스트의 길이보다 인덱스가 작을때

부모 노드의 키 를 찾기 위해선 그 인덱스에서 나누기 2를 해야하기 때무네

complete_binary_tree[index//2] 을 사용하여 인덱스 값을 반으로 나눈 값을 리턴한다

만약 인덱스 값이 리스트의 길이 범위에 있지 않으면 else 문으로 None 을 리턴한다.

cbt라는 리스트는 규칙에 따라 첫번째에는 None 을 넣었다.

첫번째 프린트문에서는 인덱스가 1이므로 1//2= 1/2이므로 해당하는 키가 없어 None 으로 리턴된것 같다(?)

두번째 프린트문은 2//1=1 이므로 인덱스 1에 해당하는 키 A가 출력되었다.

 

문제10

배열을 이용한 완전이진트리에서 왼쪽자식 노드의 키를 리턴하는 함수를 작성하시오.

 

***결과***
B
D
J
None
None

동일하게 먼저 if 문으로 인덱스의 범위가 리스트 길이 안이라면, 

여기에서 왼쪽 자식 노드를 찾아야 하기에 인덱스에 곱하기 2를 해준다

리턴 값도 동일하게 리스트의 인덱스값에 곱하기 2를 한 값을 리턴한다.

리스트 범위에 있지않으면 동일하게 else 문을 통해 None을 리턴해준다.

 

만약 오른쪽 자식노드의 키를 리턴하는 함수를 만들고 싶다면, 인덱스에 곱하기 2에 1을 더하면 된다.

 

오른쪽 자식 노드 찾기

문제12

배열을 이용한 완전이진트리에서 노드의 level을 리턴하는 함수를 작성하시오.

• 파라미터:
  • complete_binary_tree: 리스트
  • index: 인덱스
• 리턴:
  • index에 위치한 노드의 레벨

결과

0
1
2
2
3

레벨(level)

루트에서 얼마나 멀리 떨어져 있는 지를 나타내는 것 (루트 기준)

깊이 (depth)라고도 한다

루트의 레벨은 0이다 

루트에서 간선이 하나씩 아래로 뻗어 내려갈 떄마다 레벨이 1씩 증가

여기서 레벨의 뜻 짚고넘어가기!!

먼저 동일하게 인덱스의 범위를 if 문을 통해 리스트의 길이로 제한해주고 

level 의 초깃값을 0 으로 둔다. A의 인덱스값은 1이 기에  while문에 안들어가고 초깃값인 0이 나온다.

while 문으로 인덱스 값이 1보다 크면 인덱스를 2로 나눈 값이 1보다 작아질때 까지 계속 돈다.

예를 들어 인덱스 값이 6인 F는 와일문에 처음 들어값을 때 몫이 3이 되어 level 이 1 커지고, 두번째 들어갔을때는 몫이 1로 되고 level 값을 또 1 더해 2가 된다. 그 이후로는 인덱스 값이 1 이 되었으므로 1보다 크지 않아 와일문은 중단되고 level값을 리턴하면 F의 레벨인 2가 나온다.

 

 

의문점

배열을 이용한 완전이진트리 구현시 왜 인덱스0인 자리는 비우 (None 값으로 둔다)는가?

문제 12 번에서만 if문의 인덱스 조건을 0 보다 크다고 설정해놓은것은 무슨 이유 때문인가?

알거같기도 한데 교수님한테 한번 더 확실하게 여쭤봐야겠다