[좌충우돌, 파이썬으로 자료구조 구현하기] 순회 함수 만들기 (스택)

스택을 이용한 전위 순회

기본 원리는 재귀함수를 호출하는 코드 대신 방문할 노드를 스택에 저장하는 코드로 바꾸고, 스택이 빌 때까지 반복문으로 순회하는 것이다.

• 결과를 담을 빈 리스트와 스택 리스트에 루트 인덱스인 0으로 초기화한다.
• 빈 스택이 아니면 계속 반복한다.
  • 스택에서 인덱스 꺼내 parent에 대입
  • 현재 인덱스의 노드를 방문(리스트에 추가)한다.
  • 왼쪽과 오른쪽 노드의 인덱스를 구한다.
  • 각 노드의 인덱스가 배열의 크기보다 작고, 노드의 값이 None이 아니면 스택에 추가한다.
  • 스택은 마지막 원소를 먼저 꺼내므로, 오른쪽ㅈ 보다 왼쪽을 먼저 방문하려면 오른쪽 노드의 인덱스를 먼저 넣어야 한다.
• 결과 리스트 반환

def preOrderByStack(tree):
    if not tree:
        return []
    res, stack= [], [0]

    while stack: # 빈 리스트는 false
        parent = stack.pop()
        res.append(tree[parent])
        left = 2 * parent + 1
        right = left + 1
        if right < len(tree) and tree[right] is not None:
            stack.append(right)
        if left < len(tree) and tree[left] is not None:
            stack.append(left)
    return res

• stack은 후입선출이므로, left가 먼저 나오기 위해서는 right 노드를 먼저 stack에 넣어야 한다.

리팩터링

def preOrderByStack(tree):
    if not tree:
        return []
    res, stack= [], [0]

    while stack: # 빈 리스트는 false
        index = stack.pop()
        res.append(tree[index]) # 현재 노드를 넣기 위해 index 사용
        index = 2 * index + 2 # right 노드의 index로 수정
        if index < len(tree) and tree[index] is not None:
            stack.append(index)
        index -= 1 # left 노드 index로 수정
        if index < len(tree) and tree[index] is not None:
            stack.append(index)
    return res

• 굳이 parent, left, right 변수를 만들 필요가 없이 index 변수 하나만으로 표현 가능

스택을 이용한 중위 순회

중위 순회는 왼쪽 노드를 먼저 방문해야하므로, 루트 노드부터 가장 왼쪽 리프 노드가 나올 때까지 차례로 스택에 저장해서 방문을 보류한다.

• 위 그림에서 [A, B, D, G]를 스택에 넣어 방문을 보류한다.
• 더 이상 왼쪽 노드가 없으면 G를 꺼내어 방문처리를 하고 오른쪽 노드로 간다.
  • 오른쪽 노드가 없으므로 다시 스택에서 D를 꺼내 방문 처리하고 오른쪽 노드로 간다.
  • D의 오른쪽 노드가 없으므로, 스택에서 B를 꺼내 방문 처리하고 오른쪽 노드로 간다.
  • B의 오른쪽 노드인 E를 스택에 넣는다. 이 때 스택의 상태는 [A, E]이고 방문결과는 [G, D, B]이다.
• E의 왼쪽 노드가 없으므로 스택에서 E를 꺼내 방문 처리하고 오른쪽 노드로 간다.
• 위 과정을 계속 반복한다.

def inOrderByStack(tree):
    if not tree:
        return []
    index = 0
    res, stack = [], []

    while True:
        if index < len(tree) and tree[index] is not None: # 가장 왼쪽 노드까지 스택에 담으면서 이동
            stack.append(index)
            index = 2 * index + 1
        elif stack: # 가장 왼쪽 노드 도달 시 stack에 값 있는지 체크하여 결과 리스트에 추가
            index = stack.pop()
            res.append(tree[index])
            index = 2 * index + 2
        else:
            break
    return res

실행결과

>>> tree = ["A", "B", "C", "D", "E", "F", None, "G"]
>>> print(inorder(tree))

['G', 'D', 'B', 'E', 'A', 'F', 'C']

• 반복한다.
  • 현재 인덱스가 범위 내에 있고 노드가 None이 아니면
    • 현재 인덱스를 스택에 저장
    • 왼쪽 인덱스를 구하여, 왼쪽 노드로 간다.
  • 현재 인덱스의 노드가 없고, 스택에 값이 있으면
    • 스택에서 인덱스를 꺼내고
    • 해당 인덱스의 노드를 방문
    • 오른쪽 노드의 인덱스를 구하여, 오른쪽 노드로 간다.
  • 스택이 비어있다면 반복문을 벗어난다.
• 결과 리스트 반환

스택을 이용한 후위 순회

전위 순회의 결과는 부모 -> 왼쪽 -> 오른쪽이고 후위 순회의 결과는 왼쪽 -> 오른쪽 -> 부모이다. 즉, 전위 순회할 때, 부모 -> 오른쪽 -> 왼쪽으로 순서를 바꿔서 순회한 결과는 뒤집으면 후위 순회 결과이다.

파이썬 리스트 슬라이싱 기능으로 리스트를 뒤집어서 나타내보자.

def postOrderByStack(tree):
    if not tree:
        return []

    res, stack = [], [0]

    while stack:
        index = stack.pop()
        res.append(tree[index])
        index = 2 * index + 1
        if index < len(tree) and tree[index] is not None:
            stack.append(index)
        index += 1
        if index < len(tree) and tree[index] is not None:
            stack.append(index)

    return res[::-1]

• reverse 메소드나 reversed() 대신 슬라이싱을 활용하였다.

리스트를 뒤집는 방법

listA = [1,2,5,10,20]

listB = list(reversed(listA)) # [20, 10, 5, 2, 1]
listC = listA[::-1] # [20, 10, 5, 2, 1]

• reverse() 메소드를 사용하게 되면 listA 원본 데이터를 뒤집는다.

큐를 이용한 레벨 순서 순회

과정을 나열하면 다음과 같다.

• 루트부터 방문한다. 루트의 왼쪽과 오른쪽을 방문한다.
• 루트 왼쪽 노드의 왼쪽과 오른쪽을 방문한다.
• 루트 오른쪽 노드의 왼쪽과 오른쪽을 방문한다.

즉, 현대 노드를 방문할 때 현재 노드의 왼쪽과 오른쪽 노드를 차례로 큐에 넣어둔다. 큐에서 순서대로 꺼내서 같은 방식으로 처리한다.

def levelOrder(tree):
    if not tree:
        return []

    res, queue = [], [0]

    while queue:
        index = queue.pop(0)
        res.append(tree[index])
        index = 2 * index + 1
        if index < len(tree) and tree[index] is not None:
            queue.append(index)
        index += 1
        if index < len(tree) and tree[index] is not None:
            queue.append(index)
    return res

실행결과

>>> tree = ["A", "B", "C", "D", "E", "F", None, "G"]
>>> print(levelorder(tree))

['A', 'B', 'C', 'D', 'E', 'F', 'G']