똑똑한 코드 작성을 위한 실전 알고리즘

184

똑똑한 코드 작성을 위한 실전 알고리즘

6.1

시작하기

연결 리스트와 배열은 정보를 선형 배치해 저장한다. 이 장에서는 컴퓨터 과학 분야에서 중요

한 개념인 재귀 자료구조의

이진 트리

binary

tree

를 소개한다.

5

장에서는 ‘자신을 호출하는 함수’라

는

재귀

의 개념을 학습했다. 이번 장에서는 이진 트리가 재귀 자료구조라는 것을 배운다. 즉,

이진 트리는 다른 이진 트리 구조를 참조한다는 의미다. 재귀 자료구조의 개념을 소개하기에

앞서 이미 학습한 연결 리스트 자료구조를 다시 한번 살펴보자.

연결 리스트는 각 노드에 하위 리스트의 첫 번째 노드를 참조하는

next

를 가지므로 재귀 자료

구조의 예가 된다. 연결 리스트는 값이

N

개인 컬렉션의 동적인 증가 및 축소를 지원해 고정 길

이 배열을 개선한다. [코드

6

-

1

]에서

sum

_

list

()

재귀 함수는 연결 리스트 내 값들의 총합을

반환한다. 이 구현을 전통적인 순회 방식과 비교해서 보자.

코드

6-1

연결 리스트 내 값들의 총합을 구하는 재귀 및 순회 함수

class Node:

def __init__(self, val, rest=None):

self.value = val

self.next = rest

def sum_iterative(n):

total = 0

➊

while n:

total += n.value ...