[Python 코드 분석] 트리 구조 생성과 홀수 레벨 노드의 합계 구하기

파이썬으로 리스트(list)를 이용해 간단한 트리를 만들고, 재귀 함수를 통해 특정 조건에 맞는 노드들의 합을 구하는 코드를 분석해 보겠습니다.

코드는 간결하지만 트리 구조의 생성 원리와 재귀 함수의 동작 방식을 이해하는 데 아주 좋은 예제입니다.

 

전체 코드 및 실행 결과

먼저 분석할 전체 코드와 그 결과를 확인해 보겠습니다.

# 트리의 기본 단위가 되는 노드 클래스
class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

# 리스트를 받아 트리 구조로 만들어주는 함수
def tree(li):
    nodes = [Node(i) for i in li]
    # 리스트의 1번 인덱스부터 시작하여 부모-자식 관계를 연결
    for i in range(1, len(li)):
        # 부모 노드의 인덱스를 계산하여 자식 노드를 추가
        nodes[(i - 1) // 2].children.append(nodes[i])
    # 0번 인덱스의 노드(루트)를 반환
    return nodes[0]

# 트리를 순회하며 값을 계산하는 재귀 함수
def calc(node, level=0):
    # 노드가 없으면 0을 반환 (재귀의 탈출 조건)
    if node is None:
        return 0
    
    # 현재 노드의 레벨이 홀수이면 값을 더하고, 짝수이면 0을 더함
    current_value = (node.value if level % 2 == 1 else 0)
    
    # 모든 자식 노드에 대해 재귀적으로 calc 함수를 호출하고 그 합을 더함
    children_sum = sum(calc(n, level + 1) for n in node.children)
    
    return current_value + children_sum

# 분석할 데이터 리스트
li = [3, 5, 8, 12, 15, 18, 21]

# 리스트로 트리 생성
root = tree(li)

# 계산 실행 및 결과 출력
print(calc(root))

 

코드 해설

결과가 왜 13이 나왔을까요? 코드를 세 부분으로 나누어 자세히 살펴보겠습니다.

1. tree(li) 함수 - 리스트를 트리로 변환

이 함수의 역할은 평범한 1차원 리스트를 트리 자료구조로 바꾸는 것입니다.

• nodes = [Node(i) for i in li]: 리스트의 각 값을 value로 갖는 Node 객체들을 만듭니다.
• for i in range(1, len(li)): li[1]부터 순회하며 각 노드의 부모를 찾아 연결합니다.
• nodes[(i - 1) // 2]: 이 부분이 핵심입니다. 이 공식은 리스트를 완전 이진 트리로 간주했을 때, 자식 인덱스 i를 통해 부모 인덱스를 찾는 방법입니다.

li = [3, 5, 8, 12, 15, 18, 21] 리스트가 tree 함수를 통해 다음과 같은 구조로 만들어집니다.

       3  (Level 0)
      / \
     5   8  (Level 1)
    / \ / \
  12 15 18 21 (Level 2)

 

2. calc(node, level=0) 함수 - 홀수 레벨 노드의 합 계산

이 함수는 생성된 트리를 순회하며 특정 조건에 맞는 노드의 값만 더합니다.

• 재귀 함수: 함수 내부에서 자기 자신(calc)을 다시 호출하여 모든 자식 노드를 방문합니다.
• level=0: 트리의 깊이(레벨)를 추적하는 변수입니다. 루트 노드는 0부터 시작합니다.
• if level % 2 == 1: 계산의 핵심 조건입니다. 노드의 level이 홀수(1, 3, 5...)일 때만 해당 노드의 value를 합산에 포함시킵니다.

 

3. 단계별 실행 과정 분석

위 두 가지를 바탕으로 calc(root)의 계산 과정을 따라가 봅시다.

1. calc(node=3, level=0) 호출
   • level이 0 (짝수)이므로 node.value인 3은 더하지 않습니다. (현재 값: 0)
   • 자식 노드인 5와 8에 대해 calc를 재귀 호출합니다.
   • return 0 + calc(node=5, level=1) + calc(node=8, level=1)
2. calc(node=5, level=1) 호출
   • level이 1 (홀수)이므로 node.value인 5를 더합니다. (현재 값: 5)
   • 자식 노드인 12와 15에 대해 calc를 재귀 호출합니다.
   • return 5 + calc(node=12, level=2) + calc(node=15, level=2)
3. calc(node=8, level=1) 호출
   • level이 1 (홀수)이므로 node.value인 8을 더합니다. (현재 값: 8)
   • 자식 노드인 18과 21에 대해 calc를 재귀 호출합니다.
   • return 8 + calc(node=18, level=2) + calc(node=21, level=2)
4. level=2의 노드들 (12, 15, 18, 21)
   • 이 노드들은 모두 level이 2 (짝수)이므로 자신의 값을 더하지 않습니다.
   • 또한 자식 노드가 없으므로, 모두 0을 반환합니다.
5. 최종 합산
   • calc(node=5, ...)의 최종 결과: 5 + 0 + 0 = 5
   • calc(node=8, ...)의 최종 결과: 8 + 0 + 0 = 8
   • 맨 처음 calc(root, ...)의 결과: 0 + 5 + 8 = 13