N이 주어졌을 때 완전 이진 트리로 만든 이진 탐색 트리의 루트에 저장된 값과 N/2번 노드(N이 홀수 인 경우 소수점 버림)에 저장된 값을 출력하는 프로그램을 만드시오.
1부터 N까지의 자연수를 이진 탐색 트리에 저장
왼쪽 서브 트리의 루트 노드의 값 < 현재 노드의 값 < 오른쪽 서브트리의 루트 노드의 값
공유가 안된다...
중위 탐색 방식으로 값을 넣어주면 될 것 같은데?
입력 값
출력 값
# 중위 탐색
def inorder(node_idx):
global number
if 1 <= node_idx and node_idx <= N:
inorder(left[node_idx])
tree[node_idx] = number
number += 1
inorder(right[node_idx])
T = int(input())
for tc in range(1, T + 1):
# N: 노드의 개수
N = int(input())
# 관계도를 저장할 배열
left = [0] * (N + 1)
right = [0] * (N + 1)
# 값을 저장할 트리 배열
tree = [0] * (N + 1)
for i in range(1, N + 1):
if i * 2 < N + 1:
left[i] = i * 2
if i * 2 + 1 < N + 1:
right[i] = (i * 2) + 1
# 트리에 저장할 값 (1부터 시작)
number = 1
inorder(1)
print(f"#{tc}", tree[1], tree[N // 2])
# 중위탐색
def inorder(node_idx):
global number
if 1 <= node_idx and node_idx <= N:
# 왼쪽
left_c_idx = node_idx * 2
if 0 < left_c_idx < N + 1:
inorder(left_c_idx)
tree[node_idx] = number
number += 1
# 오른쪽
right_c_idx = node_idx * 2 + 1
if 0 < right_c_idx < N + 1:
inorder(right_c_idx)
T = int(input())
for tc in range(1, T + 1):
# N: 노드의 개수
N = int(input())
# 값을 저장할 트리 배열
tree = [0] * (N + 1)
number = 1
inorder(1)
print(f"#{tc}", tree[1], tree[N // 2])