[데이터구조] 트리, 트리순회, 재귀호출

트리

대표적인 자료구조 4가지

• 스택 : 마지막에 들어온 녀석이 먼저 나감
• 큐 : 먼저 들어온 녀석이 먼저 나감
• 트리 : 정점과 간선으로 이루어진 자료구조

트리의 용어

• 정점 : Node
• 간선 : 정점과 정점을 잇는 선

• 부모노드 : 바로 위에 달려있는 노드. 예) 2번과 3번노드는 1번 노드를 부모노드로 가짐
• 자식노드 : 바로 아래에 달려있는 노드. 예) 1번 부모노드의 자식노드는 2번과 3번 노드

• 레벨 : 노드의 높이를 의미

트리의 경우 트리 안에 또다른 트리가 존재 (트리의 재귀적 성질)

그렇다면, 트리를 왜 사용하는 것일까요?

• 정점에 무슨 자료를 담는가? : 코드가 실행되는 상태
• 간선은 어떤 의미인가? : 코드 A가 코드 B를 부른다.
• 즉, 트리를 보면 컴퓨터가 코드를 어떻게 실행시키는지에 대한 상태를 알려주는 구조입니다.

아래의 Factorial 예시와 같이 순차적으로 Factorial(n)을 호출하고, 마지막 Factorial(0)부터 거꾸로 계산을 진행하는 것처럼 트리를 통해서 컴퓨터가 어떻게 계산하는지 알 수 있습니다.

트리 순회

• 의미 : 트리 내에 어떠한 자료가 담겨있는지를 알기 위함
• 트리 순회의 종류
  • 전위순회 : Root - L - R
  • 중위순회 : L - Root - R
  • 후위순회 : L - R - Root

전위순회의 순서 (1 - 2 - 4 - 5 - 3 - 6 - 7)

중위순회의 순서 (4 - 2 - 5 - 1 - 6 - 3 - 7)

후위순회의 순서 (4 - 5 - 2 - 6 - 7 - 3 - 1)

기존의 스택, 큐와 같이 선형형태의 자료구조는 리스트를 통해서 만들 수 있었는데, 트리는 직접 구조를 만들어줘야합니다. Tree의 경우 3가지 값을 가지는데, 자신의 위치를 가르치는 루트의 번호와 left, right는 자식노드를 가르킵니다. (자식노드의 루트의 번호가 아니라 자식노드 전체의 트리를 가르킵니다.)

[예제 1] 이진트리 순회 구현

이번 예제에서는 이진트리를 순회하는 프로그램을 작성합니다.

주어진 이진트리를 전위순회, 중위순회, 후위순회 한 결과를 출력하세요.

[입력값] 〔1〕 n: 노드의 개수
〔2~〕 a b c
정점 a가 왼쪽 자식으로 b, 오른쪽 자식으로 c를 갖는다는 의미입니다. 만약 노드의 자식 노드가 없다면 -1이 주어집니다.

[결과값] 〔1〕 전위순회 한 결과
〔2〕 중위순회 한 결과
〔3〕 후위순회 한 결과

테스트 예제

[입력 예시]

5
1 2 3
2 4 5
3 -1 -1
4 -1 -1
5 -1 -1

[출력 예시]

1 2 4 5 3
4 2 5 1 3
4 5 2 3 1

코드

class Tree:
    def __init__(self, i, l, r) :
        self.index = i
        self.left = l
        self.right = r

    def addNode(self, i, l, r) :
        '''
        트리 내의 정점 i에 대하여 왼쪽자식을 l, 오른쪽 자식을 r로
        설정해주는 함수를 작성하세요.
        '''
        # index 중심 노드가 i인지 확인 
        if self.index == i or self.index == None: 
            self.index = i 
            self.left = Tree(l, None, None) if l != None else None 
            self.right = Tree(r, None, None) if r != None else None 
            return True 
        # Tree 탐색이 종료되는 지점도 확인 
        ## Tree에서 i가 어디에 있는지 모르니 찾는 과정부터 필요함 
        else: 
            # 추가를 했는지, 안했는지에 대한 여부를 확인해주는 코드 
            flag = False
            # 왼쪽 서브트리에서 찾아서 넣어줘라 
            ## 왼쪽 서브트리에서 i를 인덱스로 가지는 노드를 찾고 왼쪽과 오른쪽 자식 노드로 l, r를 넣어라 
            if self.left != None: 
                flag = self.left.addNode(i, l, r)
            # 오른쪽 서브트리에서 찾아서 넣어줘라 
            ## 오른쪽 서브트리에서 i를 인덱스로 가지는 노드를 찾고 왼쪽과 오른쪽 자식 노드로 l, r를 넣어라 
            if self.right != None: 
                flag = self.right.addNode(i, l, r)
            return flag 

def preorder(tree) :
    '''
    tree를 전위순회 하여 리스트로 반환하는 함수를 작성하세요.
    '''
    result = []
    result += [tree.index]
    if tree.left != None: 
        result += preorder(tree.left)

    if tree.right != None: 
        result += preorder(tree.right)
    return result

def inorder(tree) :
    '''
    tree를 중위순회 하여 리스트로 반환하는 함수를 작성하세요.
    '''
    result = []

    if tree.left != None: 
        result += inorder(tree.left)

    result += [tree.index]

    if tree.right != None: 
        result += inorder(tree.right)
    return result

def postorder(tree) :
    '''
    tree를 후위순회 하여 리스트로 반환하는 함수를 작성하세요.
    '''
    result = []

    if tree.left != None: 
        result += postorder(tree.left)

    if tree.right != None: 
        result += postorder(tree.right)

    result += [tree.index]
    return result

def main():
    myTree = Tree(None, None, None)

    n = int(input())

    for i in range(n) :
        myList = [int(v) for v in input().split()]

        if myList[1] == -1 :
            myList[1] = None

        if myList[2] == -1 :
            myList[2] = None

        myTree.addNode(myList[0], myList[1], myList[2])

    print(*preorder(myTree))
    print(*inorder(myTree))
    print(*postorder(myTree))


if __name__ == "__main__":
    main()

출처

• Elice Academy | 데이터구조 - 트리, 트리순회, 재귀호출