c언어로 쉽게 풀어쓴 자료구조 연습문제 10번, 11번

소개

"c언어로 쉽게 풀어쓴 자료구조 연습문제 10번, 11번"에 대한 내용입니다.

목차

1. 다음의 이진트리에 대하여 다음 질문에 답하여라.
(1) 위의 트리를 1차원 배열로 표현하시오
(2) 위의 트리를 전위 순회한 결과를 쓰시오.
(3) 위의 트리를 후위 순회한 결과를 쓰시오.
(4) 위의 트리를 중위 순회한 결과를 쓰시오.
(5) 위의 트리를 레벨 순회한 결과를 쓰시오.
(6) 위의 트리는 이진 탐색 트리인가? 아니라면, 그 이유는?

2. 다음 순서로 자료가 입력되었다고 가정하여 이진 탐색 트리를 생성하라
(1) 생성된 이진탐색트리를 구하시오.
(2) 여기서 11을 삭제하면 어떻게 변경되는가?
(3) 여기서 12를 추가하면 어떻게 변경되는가?
(4) 생성된 이진탐색트리에서 8을 탐색할 때 거치는 노드들을 나열하시오.
(5) 생성된 이진탐색트리를 1차원 배열을 이용하여 저장하고, 저장된 결과를 그리시오.

본문내용

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

Root node의 값은 인덱스 [1]에 저장되고, 인덱스에 저장되는 순서는 level을 기준으로 순차적으로 나눠지고, node게 저장된 값이 없을땐 해당 인덱스를 뛰어 넘어서 저장한다.

<중 략>

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

전위 순회는 현재 노드 -> 왼쪽 가지-> 오른쪽 가지의 순서로 root node를 먼저 방문한 후 왼쪽 하위 트리부터 방문하는 순회이다. 이때 반복해서 방문하는 node는 중복해서 적지 않는다.

정답: 6-4-2-1-3-5-9-7-10-8-11

참고자료

· 없음