[자료구조] Binary Tree(이진트리) 구현과 traversal(순회) 구현 python

[자료구조] Binary Tree(이진트리) 구현과 traversal(순회) 구현 python

 

 

살펴볼 주요 개념:

- Binary Tree 구현 방법

- Tree traversal의 종류와 구현 방법

 

1. Binary Tree 구현 방법

리스트, 재귀적 리스트, 노드 클래스 구현의 방법이 있다.

 

노드 클래스 구현만 살펴본다.

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

    def __str__(self):
        return str(self.key)

 

2. Tree traversal의 종류와 구현 방법

Traversal(순회) : 노드들을 순서에 따라 방문하며 key 값을 출력하는 것.

preorder, inorder, postorder가 있다.

 

preorder(전위 순회) : M -> L -> R 순서로 순회

inorder(중위 순회) : L -> M -> R 순서로 순회

postorder(후위순회) L -> R -> M 순서로 순회

 

 

 

이진트리 순회를 해볼 예제 노드

 

preorder : F -> B -> A -> D -> C -> E -> G -> H -> I

inorder :  A -> B -> C -> D -> E -> F -> G -> I -> H

postorder : A -> C -> E -> D -> B -> I -> H -> G  -> F

 

이진트리를 이렇게 순서로 나열할 수도 있지만, 순서를 다시 이진트리로 그리는 것도 가능하다.

 

 

 

 

* 전위, 중위, 후위 순회 구현

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
        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)

 

 

 

++ 위와 같은 순회는 깊이 우선 탐색(DFS)에서 사용된다.