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

재귀함수를 사용하여 전위 순회, 중위 순회, 후위 순회를 구현해보자.

전위 순회 함수 만들기

현재 노드 방문 -> 왼쪽 노드 방문 -> 오른쪽 노드 방문

위 순서를 재귀적으로 진행하면 된다.

def preOrder(tree,i=0):
    if i < len(tree):
        print(tree[i], end=", ") # 방문 처리(출력)
        left = 2 * i + 1
        right left + 1
        if left < len(tree) and tree[left] is not None:
            preOrder(tree,left)
        if right < len(tree) and tree[right] is not None:
            preOrder(tree, right)

실행 결과

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

A B D G E C F

방문 결과 리스트로 반환하기 - 1

def preorder(tree, i=0):
    if i < len(tree):
        res = [tree[i]]
        left = 2 * i + 1
        right = left + 1    
        if left < len(tree) and tree[left] is not None:
            res += preorder(tree, left)
        if right < len(tree) and tree[right] is not None:
            res += preorder(tree, right)
        return res

• 위 방법으로 방문 결과를 리스트로 받아 볼 수 있다.
• 하지만 재귀함수가 돌면서 res를 계속해서 새로 만들고 더하는 과정이 반복되서 코드를 개선해보았다.

방문 결과 리스트로 반환하기 - 2

def preorder(tree):
    def _preorder(tree, i = 0):
        if i >= len(tree) or tree[i] is None: #인덱스를 벗어나거나, 원소가 None이면 종료
            return
        res.append(tree[i]) # 현재노드 추가
        left = 2 * i + 1
        right = left + 1    
        _preorder(tree, left) # left 노드 추가
        _preorder(tree, right) # right 노드 추가

    res = []    
    _preorder(tree)
    return res

• 내부함수를 만들어서 res라는 지역변수에 할당하고 res를 반환하는 형태로 수정
• 매번 tree[left], tree[right]가 None인지 판단해주는 중복 로직을 개선했다.

중위 순회 함수 만들기

이미 작성한 전위 순회 함수에서 자신을 재귀호출하는 순서만 바꾸면된다.

중위 순회 함수는 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드 순으로 방문한다.

def inOrder(tree):
    def _inOrder(tree,i=0):
        if i >= len(tree) or tree[i] is None:
            return

        left = 2 * i + 1
        right = left + 1
        _inOrder(tree,left) # left 노드 추가
        res.append(tree[i]) # 현재 노드 추가
        _inOrder(tree,right) # right 노드 추가

    res = []
    _inOrder(tree)
    return res

실행 결과

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

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

후위 순회 함수 만들기

방문하는 코드의 위치만 바꾼다.

왼쪽 노드 방문 -> 오른쪽 노드 방문 -> 현재 노드 방문

def postorder(tree):
    def _postorder(tree, i = 0):
        if i >= len(tree) or tree[i] is None:
            return
        left = 2 * i + 1
        right = left + 1
        _postorder(tree, left) # left 노드 방문
        _postorder(tree, right) # right 노드 방문
        res.append(tree[i]) # 현재 노드 방문

    res = []    
    _postorder(tree)
    return res