SWEA_5176_이진탐색

N이 주어졌을 때 완전 이진 트리로 만든 이진 탐색 트리의 루트에 저장된 값과 N/2번 노드(N이 홀수 인 경우 소수점 버림)에 저장된 값을 출력하는 프로그램을 만드시오.

1부터 N까지의 자연수를 이진 탐색 트리에 저장

왼쪽 서브 트리의 루트 노드의 값 < 현재 노드의 값 < 오른쪽 서브트리의 루트 노드의 값

문제 링크🤓

공유가 안된다...

문제를 보고 든 생각🥺

• 중위 탐색 방식으로 값을 넣어주면 될 것 같은데?

• 입력 값

  • N: 노드의 개수

• 출력 값

  1. 트리의 루트에 저장된 값
  2. N // 2 번 노드에 저장된 값

통과한 코드😁

# 중위 탐색
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])

• 완전 이진 트리이므로, key를 이용하여 부모-자식 관계를 저장하는 left와 right 배열이 따로 필요하지 않다.

수정한 코드🤗

# 중위탐색
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])