트리 - 계층 구조와 탐색

이 장에서 배우는 것

폴더 목록을 화면에 표시할 때는 이름만 나열하는 것으로 부족하다. 어느 폴더 안에 무엇이 들어 있는지, 시작점에서 얼마나 내려가야 하는지도 드러나야 한다. 앞 장에서 다룬 그래프가 연결 자체를 표현했다면, 이 장에서는 연결에 순환이 없는 구조를 다룬다. 전공 수업에서는 이 구조를 트리(tree)라고 부른다. 폴더, 메뉴, 댓글처럼 위아래 관계가 있는 데이터를 표현할 때 자주 사용한다.

트리를 공부하는 목적은 모양을 외우는 데 있지 않다. 어떤 데이터를 트리로 다룰 수 있는지 판단하고, 구조를 빠짐없이 방문하며, 깊이의 기준을 코드로 고정하는 데 있다. 작은 자료를 직접 만들어 성질을 확인한 뒤, 폴더 구조와 깊이를 출력하는 프로그램으로 연결한다.

• 연결되어 있고 순환이 없는 구조를 구별하고, 정점 수와 간선 수의 관계를 확인한다.
• 루트를 정한 뒤 부모, 자식, 깊이, 높이를 계산한다.
• 이진 트리와 신장 트리가 각각 무엇을 뜻하는지 코드로 확인한다.
• 폴더 구조를 일정한 순서로 출력하고 각 항목의 깊이와 전체 최대 깊이를 구한다.

문제 상황

작업 도구에 프로젝트 구조 미리보기를 넣는다고 하자. 최상위 폴더는 workspace이고 그 안에 docs, src, README.md가 있다. docs에는 guide.txt가 있고, src에는 app.py와 utils 폴더가 있다. utils 안에는 text.py가 들어 있다. 사용자는 이름뿐 아니라 포함 관계를 보고 싶어 하며, 개발자는 폴더가 지나치게 여러 겹으로 만들어졌는지도 확인하려 한다.

실제 디스크를 바로 읽으면 실행한 컴퓨터마다 결과가 달라진다. 이 장에서는 같은 폴더 구조를 메모리에 직접 만든다. 따라서 파일을 생성하거나 디스크를 검색하지 않는다. 어느 컴퓨터에서 실행해도 출력이 같고, 항목 하나를 바꿨을 때 깊이가 어떻게 달라지는지도 비교하기 쉽다.

여기서 해결할 문제는 세 가지다. 첫째, 구조가 정말 트리인지 확인해야 한다. 둘째, 같은 항목을 중복해서 세지 않으며 모든 항목을 방문해야 한다. 셋째, 화면의 들여쓰기와 계산한 깊이가 같은 기준을 사용해야 한다. 이름을 보기 좋게 출력하는 일과 구조의 의미를 정확히 정하는 일은 함께 진행해야 한다.

트리를 판별하는 두 조건

정점은 연결의 대상이고, 간선은 두 정점을 잇는 연결이다. 이 장에서는 방향을 붙이지 않은 간선을 기준으로 트리를 정의한다. 어떤 정점에서 출발해도 다른 모든 정점으로 갈 수 있으면 연결되어 있다고 한다. 간선을 되짚는 움직임을 제외하고, 서로 다른 정점을 따라가다가 출발점으로 돌아오는 길이 있으면 순환이 있다고 한다.

전공 수업에서 말하는 트리는 연결되어 있고 순환이 없는 무방향 그래프다. 이 장에서는 정점이 하나 이상이고, 자기 자신을 잇는 간선과 같은 두 정점 사이의 중복 간선이 없는 경우를 다룬다. 정점 하나만 있는 구조도 트리다. 이때 간선은 없다.

트리에서 두 정점 사이를 잇는 단순 경로는 하나뿐이다. 단순 경로는 같은 정점을 두 번 지나지 않는 길이다. 경로가 두 개라면 두 길이 갈라졌다가 다시 만나는 부분에 순환이 생긴다. 반대로 길이 하나도 없다면 연결 조건을 만족하지 못한다. 이 성질 덕분에 루트를 정하면 각 항목에 도달하는 길과 깊이가 하나로 정해진다.

간선은 왜 정점보다 하나 적은가

정점 하나에서 시작하면 간선은 0개다. 여기에 새 정점을 기존 정점 하나와 연결해서 붙일 때마다 정점과 간선이 각각 하나씩 늘어난다. 이렇게 붙이면 연결을 유지하면서 순환을 만들지 않는다. 따라서 정점 수를 n이라고 할 때 간선 수는 n - 1이다.

이 설명이 일부 모양에만 맞는 것은 아니다. 정점이 둘 이상인 유한한 트리에서 가장 긴 단순 경로를 잡으면 그 끝 정점에는 이웃이 하나뿐이다. 다른 이웃이 있으면 길을 더 늘릴 수 있거나 순환이 생기기 때문이다. 끝 정점과 그 간선을 제거해도 나머지는 트리다. 이 제거를 반복하면 정점 하나가 남는다. 붙이기와 제거하기가 서로 반대 과정임을 코드의 입력 크기와 연결해 생각할 수 있다.

연결 여부와 간선 수를 함께 확인해야 트리를 판별할 수 있다

구조	정점 수	간선 수	판정
정점 하나	1	0	트리다
네 정점이 한 줄로 연결됨	4	3	트리다
삼각형과 고립된 정점	4	3	연결되지 않아 트리가 아니다
네 정점이 사각형으로 연결됨	4	4	순환이 있어 트리가 아니다

특히 세 번째 행이 작은 반례다. 간선 수가 정점 수보다 하나 적다는 검사만으로는 부족하다. 다만 앞서 정한 무방향 그래프에서는 연결되어 있다는 조건까지 확인하면 충분하다. 연결된 정점 n개를 하나의 덩어리로 묶으려면 최소 n - 1개의 간선이 필요하다. 순환이 있다면 그중 간선 하나를 빼도 연결이 유지되므로, 간선이 이미 n - 1개인 연결 그래프에는 순환이 있을 수 없다.

완성 코드의 is_tree 함수는 이 논리를 사용한다. 먼저 간선 수를 확인하고, 한 정점에서 시작해 도달한 정점 수를 센다. 삼각형과 고립된 정점을 입력하면 간선 수 검사는 통과하지만 도달한 정점 수가 부족해서 False가 나온다.

루트와 깊이, 그리고 이진 트리

트리 자체에는 맨 위가 정해져 있지 않다. 기준으로 삼을 정점 하나를 골라 루트(root)라고 부르면 위아래 관계가 생긴다. 전공 수업에서는 이렇게 기준점을 정한 구조를 루트 트리라고 부른다. 루트로 가는 길에서 바로 앞에 있는 정점은 부모이고, 반대로 한 단계 아래로 이어진 정점은 자식이다. 루트에는 부모가 없다.

루트에서 어떤 정점까지 이동한 간선 수가 그 정점의 깊이(depth)다. 이 장에서는 루트의 깊이를 0으로 정한다. 자식으로 한 번 내려가면 깊이는 1 증가한다. 같은 구조라도 루트를 바꾸면 부모와 깊이가 달라질 수 있다. 반면 정점 수와 간선 수, 순환이 없다는 성질은 달라지지 않는다.

자식이 없는 정점은 잎이라고 부른다. 모든 정점의 깊이 중 최댓값을 이 장에서는 트리의 높이(height)로 정한다. 높이를 정점 개수로 세는 자료도 있으므로 외부 설명과 비교할 때는 기준부터 확인해야 한다. 여기서는 정점 하나만 있는 트리의 높이가 0이다. 빈 트리는 프로그램의 입력 범위에서 제외한다.

폴더를 코드로 표현하기

완성 코드에서는 각 항목을 사전으로 표현한다. 사전은 키에 값을 연결해 저장하는 Python 자료형이다. name 키에는 이름을, children 키에는 자식 항목들의 리스트를 넣는다. node["name"]은 그 항목의 이름을 꺼내는 표현이다. 이 구조에서는 파일도 자식이 없는 항목으로 표현한다.

item = {"name": "guide.txt", "children": []}
print(item["name"])
print(len(item["children"]))
# guide.txt
# 0

자식이 없는 폴더와 파일은 이름이나 자식 수만으로 구별할 수 없다. 이번 프로그램은 포함 관계와 깊이만 출력하므로 종류를 따로 저장하지 않는다. 파일에 자식을 넣지 못하게 검사해야 하는 프로그램이라면 종류를 나타내는 정보를 추가해야 한다.

같은 자식 사전을 여러 부모의 children에 넣거나, 자식에서 조상 사전을 다시 참조하게 만들 수도 있다. Python 자료형 자체가 트리 조건을 보장하지는 않는다. 완성 코드에 직접 작성한 자료는 각 항목의 부모가 하나이고 순환도 없는 것으로 구성한다. 외부에서 받은 자료를 처리할 때는 이 전제를 먼저 검사해야 한다.

이진 트리는 자식의 수와 자리를 제한한다

전공 수업에서 말하는 이진 트리(binary tree)는 각 정점에 왼쪽 자식 자리와 오른쪽 자식 자리가 있고, 각 자리에 자식이 최대 하나씩 있는 구조다. 자식이 꼭 두 명이어야 하는 것은 아니다. 자식이 하나도 없거나 한 명만 있어도 된다. 왼쪽만 있는 경우와 오른쪽만 있는 경우도 서로 구별한다.

폴더에는 자식이 세 개 이상 있을 수 있으므로 일반적인 폴더 트리는 이진 트리가 아니다. 또한 이진 트리라고 해서 값이 자동으로 정렬되는 것도 아니다. 왼쪽과 오른쪽에 어떤 값을 놓을지는 별도의 규칙이다.

다음 코드는 자식의 두 자리를 확인한다. None은 해당 자리에 값이 없음을 나타내는 Python 값이다. 완성 코드에서는 네 정점을 가진 이진 트리를 직접 만들고 깊이도 계산한다.

single = {"left": None, "right": None}
print(single["left"] is None)
print(single["right"] is None)
# True
# True

완성 코드의 binary_max_depth는 정점과 깊이를 함께 저장해 가장 큰 깊이를 찾는다. 폴더와 이진 트리의 자료 모양은 다르지만, 자식을 방문할 때 깊이를 1 증가시킨다는 원리는 같다.

신장 트리와 방문 순서

연결 그래프에는 목적지로 가는 길이 여럿 있을 수 있다. 모든 정점을 남기면서 필요한 간선만 골라 순환을 없애면 트리가 된다. 전공 수업에서는 원래 그래프의 모든 정점을 포함하는 이 구조를 신장 트리(spanning tree)라고 부른다. 새 정점을 추가하거나 원래 없던 간선을 만드는 작업은 아니다.

신장 트리는 하나로 정해지지 않을 수 있다. 사각형의 네 변으로 연결된 그래프라면 어느 한 변을 빼도 신장 트리가 된다. 선택한 간선에 따라 경로는 바뀌지만 정점 네 개와 간선 세 개라는 수는 같다. 연결되지 않은 그래프에서는 전체 정점을 포함하는 하나의 신장 트리를 만들 수 없다.

완성 코드에서는 A에서 출발해 아직 방문하지 않은 이웃을 발견할 때만 간선을 선택한다. 발견한 정점은 리스트의 뒤에 넣고, 리스트의 앞쪽부터 차례로 처리한다. 먼저 발견한 항목을 먼저 꺼내는 저장 방식을 큐(queue)라고 부른다. 가까운 깊이의 정점부터 살펴보는 이 방문 방법은 전공 수업에서 너비 우선 탐색이라고 부른다.

폴더 출력에는 다른 순서를 쓴다. docs를 출력한 뒤 그 아래의 guide.txt까지 내려갔다가 src로 이동해야 포함 관계를 읽기 좋다. 이처럼 한 갈래를 먼저 내려가는 방식은 깊이 우선 탐색이다. 나중에 넣은 항목을 먼저 꺼내는 스택(stack)을 리스트로 만들면 이 순서를 구현할 수 있다.

스택에서 마지막 항목을 꺼내는 연산은 pop()이다. 자식을 docs, src, README.md 순서로 출력하려면 스택에는 반대 순서로 넣어야 한다. reversed는 원래 자료를 뒤에서부터 읽게 하는 Python 내장 함수다. 정렬한 자식 목록을 거꾸로 넣으면 꺼낼 때는 정렬 순서가 된다.

완성 코드는 이름을 sorted로 정렬한다. 이 예제의 이름은 모두 영문이므로 같은 입력에서 순서가 일정하다. 실제 파일 탐색기의 표시 순서는 별도의 정책을 사용할 수 있다. 여기서는 이름의 대소문자 등을 바꾸지 않고 Python 문자열 비교 순서를 그대로 따른다.

실무에서 만나는 곳

폴더 미리보기, 화면의 메뉴, 문서의 절 구조는 루트를 기준으로 자식을 펼치는 문제다. 깊이는 화면 들여쓰기뿐 아니라 허용할 중첩 단계 수를 검사할 때도 쓰인다. 루트부터 최대 세 번 내려가도록 제한한다면, 깊이가 3보다 큰 항목을 찾으면 된다.

신장 트리는 여러 경로가 있는 연결 구조에서 각 대상을 한 번씩 연결하는 기본 골격을 얻을 때 쓴다. 다만 아무 신장 트리나 선택했다고 해서 연결 비용이 가장 작아지는 것은 아니다. 비용을 최소화하려면 추가 조건과 선택 방법이 필요하다. 이번 코드가 보장하는 것은 모든 정점의 연결과 순환 제거다.

계층처럼 보이는 자료라도 부모가 둘일 수 있다면 트리로 단정하면 안 된다. 하나의 작업을 여러 작업이 공통으로 필요로 하는 의존성 구조가 그 예다. 화면에서 같은 대상을 두 번 펼쳐 보여 주는 것과 실제 자료에 서로 다른 정점이 두 개 있는 것은 구별해야 한다.

완성 코드

다음 내용을 main.py에 저장한다. 외부 패키지, 네트워크, 실제 폴더 접근을 사용하지 않는다. 구조 확인 예제와 폴더 출력이 한 번 실행된 뒤 종료된다. walk와 binary_max_depth는 재귀 호출 대신 리스트를 사용하므로, 항목을 방문하는 과정에 함수 호출 깊이가 누적되지 않는다.

def is_tree(graph):
    if not graph:
        return False

    vertex_count = len(graph)
    edge_count = sum(len(neighbors) for neighbors in graph.values()) // 2
    if edge_count != vertex_count - 1:
        return False

    start = next(iter(graph))
    seen = {start}
    pending = [start]

    while pending:
        current = pending.pop()
        for neighbor in graph[current]:
            if neighbor not in seen:
                seen.add(neighbor)
                pending.append(neighbor)

    return len(seen) == vertex_count


def spanning_tree(graph, start):
    seen = {start}
    queue = [start]
    cursor = 0
    edges = []

    while cursor < len(queue):
        current = queue[cursor]
        cursor += 1
        for neighbor in sorted(graph[current]):
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)
                edges.append((current, neighbor))

    if len(seen) != len(graph):
        raise ValueError("모든 정점에 도달할 수 없다")
    return edges


def binary_max_depth(root):
    pending = [(root, 0)]
    maximum = 0

    while pending:
        current, depth = pending.pop()
        maximum = max(maximum, depth)
        for side in ("left", "right"):
            child = current[side]
            if child is not None:
                pending.append((child, depth + 1))

    return maximum


def walk(root):
    pending = [(root, 0)]

    while pending:
        current, depth = pending.pop()
        yield current["name"], depth
        children = sorted(
            current["children"],
            key=lambda child: child["name"],
        )
        for child in reversed(children):
            pending.append((child, depth + 1))


def main():
    chain = {
        "A": ["B"],
        "B": ["A", "C"],
        "C": ["B", "D"],
        "D": ["C"],
    }
    counterexample = {
        "A": ["B", "C"],
        "B": ["A", "C"],
        "C": ["A", "B"],
        "D": [],
    }
    square = {
        "A": ["B", "D"],
        "B": ["A", "C"],
        "C": ["B", "D"],
        "D": ["A", "C"],
    }

    binary = {
        "left": {
            "left": None,
            "right": {"left": None, "right": None},
        },
        "right": {"left": None, "right": None},
    }

    folder = {
        "name": "workspace",
        "children": [
            {
                "name": "src",
                "children": [
                    {
                        "name": "utils",
                        "children": [
                            {"name": "text.py", "children": []},
                        ],
                    },
                    {"name": "app.py", "children": []},
                ],
            },
            {"name": "README.md", "children": []},
            {
                "name": "docs",
                "children": [
                    {"name": "guide.txt", "children": []},
                ],
            },
        ],
    }

    print("트리 성질 확인")
    print(f"한 줄 연결: {is_tree(chain)}")
    print(f"삼각형 + 고립 정점: {is_tree(counterexample)}")
    print(f"사각형: {is_tree(square)}")
    print(f"신장 트리 간선: {spanning_tree(square, 'A')}")
    print(f"이진 트리 최대 깊이: {binary_max_depth(binary)}")

    print()
    print("폴더 구조와 깊이")
    vertex_count = 0
    maximum = 0

    for name, depth in walk(folder):
        indent = "  " * depth
        print(f"{indent}{name} (깊이 {depth})")
        vertex_count += 1
        maximum = max(maximum, depth)

    print(f"정점 수: {vertex_count}")
    print(f"간선 수: {vertex_count - 1}")
    print(f"최대 깊이: {maximum}")


if __name__ == "__main__":
    main()

줄별 해설

is_tree의 입력과 첫 검사. graph는 정점 이름을 키로, 이웃 리스트를 값으로 갖는 사전이다. 이 함수는 모든 이웃이 사전의 키로 존재하고, A의 이웃에 B가 있으면 B의 이웃에도 A가 있으며, 자기 연결과 중복 이웃이 없다는 전제를 둔다. 앞서 한정한 무방향 그래프를 표현하기 위한 약속이다. 형식이 임의로 잘못된 자료까지 검사하는 함수는 아니다.

if not graph는 빈 사전을 거른다. graph.values()는 각 정점의 이웃 리스트를 차례로 제공한다. sum 안의 표현은 그 길이를 모두 더한다. 무방향 간선은 양쪽 이웃 리스트에 한 번씩 나타나므로 합을 2로 나눈다. //는 정수 나눗셈이다. 여기서 구한 수가 정점 수보다 하나 적지 않으면 즉시 False를 반환한다.

연결 여부 확인. next(iter(graph))는 사전에서 시작 정점 하나를 가져온다. seen은 발견한 정점을 모으는 집합이다. pending은 앞으로 처리할 정점을 담는 리스트다. 이웃을 처음 발견한 순간 seen에 넣기 때문에 다른 정점에서 같은 이웃을 만나더라도 중복해서 추가하지 않는다. 반복이 끝났을 때 발견한 정점 수가 전체 정점 수와 같으면 연결된 것이다.

신장 트리의 간선 선택. spanning_tree는 시작 정점이 graph에 있다는 전제를 둔다. queue[cursor]로 아직 처리하지 않은 정점을 읽고 cursor를 1 늘린다. 리스트 앞을 매번 삭제하지 않고 읽는 위치만 이동하는 방식이다. 새 이웃을 발견하면 방문 예약과 함께 현재 정점에서 그 이웃으로 가는 간선을 기록한다.

edges.append((current, neighbor))의 안쪽 괄호는 두 값을 묶는 튜플을 만든다. 정점은 발견할 때마다 한 번씩 추가되므로 시작 정점을 제외한 모든 정점에 간선 하나씩이 대응한다. 사각형에서는 A에서 B와 D를 발견하고, 이어 B에서 C를 발견해 간선 세 개를 고른다. 발견하지 못한 정점이 남으면 ValueError라는 오류를 발생시켜 입력이 연결되지 않았음을 알린다.

이진 트리의 깊이 계산. pending에는 정점만 넣지 않고 (정점, 깊이)를 함께 넣는다. current, depth = pending.pop()은 묶인 두 값을 각각의 변수에 나누어 받는다. maximum은 지금까지 방문한 깊이의 최댓값이다. 왼쪽과 오른쪽 자리 중 None이 아닌 자식만 현재 깊이에 1을 더해 넣는다.

폴더 방문 결과 전달. walk의 yield는 결과를 하나 내보낸 뒤 함수의 진행 상태를 보관한다. 다음 결과가 필요해지면 멈춘 자리에서 이어 간다. 전공 수업과 Python 설명에서는 이런 함수를 생성기라고 부른다. main의 for문은 생성기가 내보내는 이름과 깊이를 하나씩 받아 출력한다.

sorted의 key는 정렬 기준을 지정한다. lambda child: child["name"]은 자식 하나를 받아 이름을 돌려주는 짧은 함수 표현이다. def로 별도 함수를 만드는 대신 이 자리에서 기준을 적은 것이다. reversed(children)으로 스택에 넣는 순서를 뒤집기 때문에 실제 방문 순서는 이름의 오름차순이 된다.

개수와 최대 깊이 집계. main은 항목을 출력할 때마다 vertex_count를 1 늘린다. maximum은 이전 최댓값과 현재 깊이 중 큰 값을 저장한다. 마지막 간선 수 출력은 입력이 트리라는 전제에서 정점 수 - 1을 적용한 값이다. 별도의 구조 검사를 수행한 결과로 오해하면 안 된다.

폴더 정점 수가 n이면 각 정점은 한 번씩 출력된다. 다만 각 폴더의 자식 목록을 정렬하는 작업이 추가된다. 자식이 k개인 폴더에서는 일반적으로 k log k에 비례하는 정렬 비용이 든다. 스택에는 아직 처리하지 않은 형제들도 들어가므로 저장 공간이 깊이에만 비례한다고 단정할 수 없다. 자식이 매우 많은 루트에서는 한꺼번에 많은 항목을 저장한다.

마지막 if문은 이 파일을 직접 실행했을 때 main을 호출한다. 다른 Python 파일에서 이 파일의 함수를 가져다 쓰는 경우에는 예제 출력을 자동으로 실행하지 않는다.

실행 결과

main.py를 저장한 디렉터리에서 다음 명령을 실행한다. README.md가 docs보다 먼저 출력되는 것은 이 프로그램에서 정한 문자열 정렬 순서에 따른 결과다.

python3 main.py

트리 성질 확인
한 줄 연결: True
삼각형 + 고립 정점: False
사각형: False
신장 트리 간선: [('A', 'B'), ('A', 'D'), ('B', 'C')]
이진 트리 최대 깊이: 2

폴더 구조와 깊이
workspace (깊이 0)
  README.md (깊이 1)
  docs (깊이 1)
    guide.txt (깊이 2)
  src (깊이 1)
    app.py (깊이 2)
    utils (깊이 2)
      text.py (깊이 3)
정점 수: 8
간선 수: 7
최대 깊이: 3

출력의 text.py까지는 workspace에서 간선 세 개를 지난다. 정점 이름 네 개를 지나지만 깊이는 3이다. 폴더와 파일을 모두 정점으로 세었으므로 전체 정점은 8개다. 파일을 제외한 폴더 수를 구하려면 항목 종류를 별도로 저장하고 집계 기준을 바꿔야 한다.

실무에서 자주 틀리는 것

간선 수만 보고 트리라고 판정한다

삼각형과 고립 정점은 정점 4개, 간선 3개다. 수식은 맞지만 하나의 연결 구조가 아니다. 다음 틀린 함수는 두 값을 받기만 하므로 연결 여부를 알 수 없다.

def wrong_check(vertex_count, edge_count):
    return edge_count == vertex_count - 1

print(wrong_check(4, 3))
# True

고친 코드에서는 완성 코드의 연결 검사를 함께 사용한다. 아래 코드는 main 안에서 counterexample을 만든 뒤 실행하면 된다.

print(is_tree(counterexample))
# False

무방향 간선의 양쪽 기록과 중복 여부를 확인하지 않은 채 간선 수를 절반으로 나누는 것도 피해야 한다. 계산식은 입력 표현의 약속까지 만족할 때 의미가 있다.

경로에 등장하는 정점 수를 깊이로 쓴다

루트도 방문한 항목이므로 1부터 세기 쉽다. 그러나 이 장의 깊이는 간선 수다. 다음 코드는 루트부터 1을 부여하므로 모든 깊이가 하나씩 커진다.

root = {"name": "workspace", "children": []}

pending = [(root, 1)]
current, depth = pending.pop()
print(depth)
# 1

고친 코드는 시작값을 0으로 둔다. 외부 요구가 루트를 1단계로 표시하라는 것이라면, 내부 깊이와 화면 표시값의 관계를 따로 정해야 한다.

pending = [(root, 0)]
current, depth = pending.pop()
print(depth)
# 0

스택에 정렬 순서대로 넣는다

스택은 마지막에 넣은 항목을 먼저 꺼낸다. 정렬한 목록을 그대로 넣으면 출력 순서가 뒤집힌다. 다음 두 조각은 각각 독립적으로 실행할 수 있다.

pending = []
for name in sorted(["src", "docs"]):
    pending.append(name)

while pending:
    print(pending.pop())
# src
# docs

고친 코드에서는 넣는 순서를 반대로 한다. 완성 코드에서 reversed를 사용하는 이유다.

pending = []
for name in reversed(sorted(["src", "docs"])):
    pending.append(name)

while pending:
    print(pending.pop())
# docs
# src

이진 트리의 빈 자식을 정점으로 처리한다

이진 트리의 두 자리가 항상 실제 정점을 담는 것은 아니다. None도 스택에 넣으면 나중에 사전처럼 읽는 단계에서 오류가 난다. 다음 틀린 코드는 불필요한 방문 대상을 만든다.

current = {"left": None, "right": None}
pending = []

for side in ("left", "right"):
    pending.append(current[side])

print(pending)
# [None, None]

고친 코드에서는 실제 자식이 존재하는지 확인한다. 자식이 없는 정점은 이미 자신을 방문한 것으로 충분하다.

current = {"left": None, "right": None}
pending = []

for side in ("left", "right"):
    child = current[side]
    if child is not None:
        pending.append(child)

print(pending)
# []

한눈에 보기

트리의 개념을 코드에서 확인하는 위치와 기준

개념	뜻	코드의 확인 방법
트리	연결되어 있고 순환이 없는 구조	간선 수와 도달한 정점 수를 함께 검사한다
루트	부모와 깊이를 정하는 기준 정점	방문 목록에 깊이 0으로 처음 넣는다
깊이	루트에서 지난 간선 수	자식을 넣을 때 1을 더한다
높이	이 장에서는 전체 깊이의 최댓값	maximum을 방문마다 갱신한다
잎	자식이 없는 정점	자식 목록이 비었는지 확인한다
이진 트리	왼쪽과 오른쪽에 자식 자리가 있는 트리	각 자리의 None 여부를 검사한다
신장 트리	원래 그래프의 모든 정점을 포함하는 트리	새 정점 발견 때 간선을 하나 고른다

폴더 출력에서 들여쓰기는 깊이를 시각적으로 표현한 결과다. 먼저 루트와 부모 관계를 정하고 깊이를 계산한 다음 화면 모양을 만든다. 보이는 모양만으로 자료가 트리인지 판단하지 않고, 연결 관계의 조건을 먼저 확인하는 습관이 필요하다.

연습 문제

1. 완성 코드의 src 아래에 자식이 없는 config.py를 추가하라. 추가 후 정점 수, 간선 수, 최대 깊이를 예상하고 실행으로 확인하라.
2. walk를 이용해 깊이가 2인 항목의 이름만 출력하라. 이어 자식이 없는 항목의 개수를 세는 코드를 작성하라. 파일 수라고 부를 수 있는지도 설명하라.
3. 사각형 그래프의 신장 트리를 A 대신 C에서 시작해 구하라. 선택한 간선을 예측한 뒤, 시작점을 바꿔도 간선 수가 같은 이유를 설명하라.
4. 루트 하나만 있는 폴더 구조와, 루트의 왼쪽 자식만 있는 이진 트리를 각각 만들어 깊이를 계산하라. 이진 트리에서 왼쪽 자식을 오른쪽으로 옮기면 최대 깊이가 바뀌는지도 확인하라.

정답과 해설

항목 하나 추가하기

src 항목의 children 리스트에 다음 사전을 추가한다. 정렬은 walk가 수행하므로 리스트에 넣는 위치는 출력 순서에 영향을 주지 않는다.

{"name": "config.py", "children": []}

정점 수는 9, 간선 수는 8, 최대 깊이는 3이다. config.py의 깊이는 2다. 새 정점과 간선을 하나씩 추가했으므로 트리의 수 관계는 유지된다. 기존에 가장 깊던 text.py까지의 길이는 변하지 않는다.

깊이 필터와 잎 세기

다음 코드는 완성 코드의 main 안에서 folder를 만든 뒤 실행할 수 있다. 깊이 조건을 출력 조건으로만 사용하므로 다른 깊이의 항목도 계속 방문한다.

for name, depth in walk(folder):
    if depth == 2:
        print(name)
# guide.txt
# app.py
# utils

잎의 개수는 이름과 깊이만으로 알 수 없으므로 항목 자체를 방문한다. 수정 전 자료의 잎은 4개다.

pending = [folder]
leaf_count = 0

while pending:
    current = pending.pop()
    if not current["children"]:
        leaf_count += 1
    pending.extend(current["children"])

print(leaf_count)
# 4

extend는 리스트의 항목들을 다른 리스트의 뒤에 차례로 추가한다. 이 예제에서는 잎 네 개가 모두 파일이지만, 자식이 없는 폴더도 잎이다. 따라서 일반적인 입력에서 이 결과를 파일 수라고 부를 수는 없다.

시작점이 다른 신장 트리

print(spanning_tree(square, "C"))
# [('C', 'B'), ('C', 'D'), ('B', 'A')]

C의 이웃을 이름순으로 살피므로 B와 D를 먼저 발견한다. 다음으로 B를 처리할 때 A를 발견한다. 정점 네 개 중 시작 정점을 제외한 세 정점을 처음 발견할 때마다 간선 하나를 고르므로 간선은 여전히 세 개다.

가장 작은 깊이 확인

single_folder = {"name": "root", "children": []}
print(list(walk(single_folder)))
# [('root', 0)]

left_only = {
    "left": {"left": None, "right": None},
    "right": None,
}
right_only = {
    "left": None,
    "right": {"left": None, "right": None},
}
print(binary_max_depth(left_only))
print(binary_max_depth(right_only))
# 1
# 1

list는 생성기가 내보내는 결과를 리스트로 모은다. 루트 하나의 깊이는 0이며, 자식 하나까지 내려가면 최대 깊이는 1이다. 왼쪽과 오른쪽은 서로 다른 자리지만 이동한 간선 수는 같으므로 최대 깊이는 바뀌지 않는다.