파이썬) 이진 트리 깊이 우선 순회 연산

이진 트리란 트리에 포함되는 모든 노드의 차수가 2이하인 트리를 말한다. 이진 트리를 추상적 자료구조로 구현하기 위한 연산에는 세 가지가 있다.

 

• size() : 현재 트리에 포함되어 있는 노드의 수를 구함
• depth() : 현재 트리의 깊이(또는 높이)를 구함
• traversal() : 트리의 각 노드를 정해진 순서로 방문하는 연산 

 

이진 트리를 구현하기 위한 코드는 다음과 같다.

class Node:   # 빈 노드 생성

    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None
        
class BinaryTree:  # 이진 트리의 루트 노드 생성

    def __init__(self, r):
        self.root = r

 

size() 연산을 구현하기 위한 방법은 다음과 같다.

위 그림과 같이 루트 노드와 왼쪽서브트리와 오른쪽 서브트리의 노드 개수를 모두 더하면 이진 트리의 size가 나온다. 이를 재귀적인 방법을 이용해 구현한 코드는 다음과 같다.

class Node:

     def size(self): 
        l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1



class BinaryTree:

     def size(self):
        if self.root:
            return self.root.size()
        else:
            return 0

size()함수안에 size()를 이용한 코드이다. 왼쪽,오른쪽 노드가 있으면 그 노드의 size를 호출하는 방식의 코드이다. 이진 트리의 경우 루트 노드가 존재하면 size연산을 호출하는 방식이다.

 

depth() 연산을 구현한 코드는 다음과 같다.

class Node:

     def depth(self):
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0     
        return max(l,r)+1
        
 class BinaryTree:       
       
     def depth(self):
        if self.root:
             return self.root.depth()
        else:
            return 0

size연산과 비슷한데 깊이의 정의를 생각하면 리프 노드와 루프 노드 사이의 간선 개수+1이다. 그래서 왼쪽과 오른쪽 중 더 깊이가 깊은쪽의 값+1로 한 트리의 깊이를 구할 수 있다.

 

순회에는 깊이,넓이 우선 순회 두 가지 경우가 있는데 우선 깊이 우선 순회 방법을 살펴보자면

 

깊이 우선 순회에는 대표적인 세가지 방법이 있다.

• 중위 순회(in-order traversal)
• 전위 순회(pre-order traversal)
• 후위 순회(post-order traversal)

 

중위 순회

중위 순회의 순회 순서는 왼쪽 서브트리->자기 자신-> 오른쪽 서브트리이다. 이를 그림으로 설명하면 다음과 같다.

중위 순회를 구현한 코드는 다음과 같다.

class Node:

    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal
        
class BinaryTree:

    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []

마찬자기로 재귀적인 방법을 이용해 함수를 구성했다. 왼쪽 노드가 있다면 왼쪽노드에 inorder()를 호출하고 그 다음 자기 자신을 append한다. 오른쪽 노드가 있다면 오른쪽 노드에 inorder()를 호출한다.

 

 

전위 순회

전위 순회의 순회 순서는 자기 자신 -> 왼쪽 서브트리 -> 오른쪽 서브트리이다. 이를 그림으로 설명하면 다음과 같다.

전위 순회를 구현한 코드는 다음과 같다.

class Node:

    def preorder(self):
        traversal = []      
        traversal.append(self.data)
        if self.left:            
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal
        
        
class BinaryTree:

    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []

자기 자신이 순회 순서 우선순위 이므로 먼저 append한다. 그 다음 순회 순서는 왼쪽,오른쪽 서브트리 순이므로 왼쪽을 먼저 preorder()를 호출한다.

 

후위 순회

전위 순회의 순회 순서는 왼쪽 서브트리 -> 오른쪽 서브트리 -> 자기 자신이다. 이를 그림으로 설명하면 다음과 같다.

후위 순회를 구현한 코드는 다음과 같다.

class Node:

    def postorder(self):
        traversal = []
        if self.left:
            traversal += self.left.postorder()
        if self.right:
            traversal += self.right.postorder()
        traversal.append(self.data)
        return traversal
        
class BinaryTree:

    def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []

순회 순서 우선순위에 맞게 왼쪽,오른쪽으로 postorder()를 재귀적으로 호출하고 마지막 자기 자신을 append하는 식으로 구성 되어 있다.

 

위 세 순회의 코드를 보면 순회 순서에 맞게 자기 자신, 왼쪽, 오른쪽 서브트리에 해당하는 코드를 옮겨주면 구현이 된다.