이진트리 순회 ( Preorder, Inorder, Postorder )

이진트리에 대해 궁금하다면?? 👇🏻👇🏻

https://p-james-y.tistory.com/6

이진트리 ( binary tree ) 표현법

 

트리 순회란 ( tree traversal ) 각 노드를 한번씩 방문하는 것을 말한다

 

트리순회를 알아보기 전에 노드 클래스를 간단히 구현해보면 각각의 노드에는 key 가 있고, parent, left, right 링크가 존재합니다.

그림으로 알아보면 다음과 같습니다.

노드

노드를 클래스로 구현하면 다음과 같습니다.

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    def __str__(self):
        return str(self.key)

 

이제 이진트리 순회 방법을 알아보겠습니다. 이진트리를 순회하는 방법은 3가지 (Preorder, Inorder, Postorder) 가 있습니다. 트리는 다음과 같이 순회하는 지점(M) 과 순회하는 지점의 왼쪽 서브트리(L), 오른쪽 서브트리(R) 로 나타낼수 있습니다.

트리구성

 

다음의 이진트리를 3가지 방법으로 방문해보겠습니다.

 

1. Preorder

M → L → R 순으로 방문하는 것입니다.

F → B → A → D → C → E → G → I → H

2. Inorder

L → M → R 순으로 방문하는 것입니다.

A → B → C → D → E → F → G → H → I

2. Postorder

L → R → M 순으로 방문하는 것입니다.

A → C → E → D → B → H → I → G → F

 

3가지 방법의 공통점은 항상 왼쪽 서브트리(L)를 오른쪽 서브트리(R)보다 먼저 방문한다는 것입니다.

3가지 순회 방법을 Node 클래스로 구현해보겠습니다.

class Node:
     def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
        
    def __str__(self):
        return str(self.key)

    def preorder(self): # 현재 방문중인 노드 = self, MLR
        if self != None:
            print(self.key)
            if self.left:
                self.left.preorder()
            if self.right:
                self.right.preorder()

    def inorder(self):
        if self != None:
            if self.left:
                self.left.inorder()
            print(self.key)
            if self.right:
                self.right.inorder()

    def postorder(self):
        if self != None:
            if self.left:
                self.left.postorder()
            if self.right:
                self.right.postorder()
            print(self.key)

Reference

https://www.youtube.com/watch?v=HDjqrmmpFdU&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=25