[파이썬 자료구조] 이진 트리 (Binary Tree) - 코드 구현(size, depth, travelsal)

1. 이진 트리의 추상적 자료구조

연산의 정의

• size() - 현재 트리에 포함되어 있는 노드의 수를 구함
• depth() - 현재 트리의 깊이를 구함
• 순회(travelsal)

 

우선 size와 depth를 구현하는 이진트리 코드를 작성해 보겠습니다.

class Node:

    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None


    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


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


class BinaryTree:

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

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


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

 

Traversal (순회) 의 코드는 이보다 좀더 복잡 합니다.

우선 순회를 구현하는 코드는 크게 두가지로 나눌 수 있습니다.

깊이 우선 순회와 넓이 우선 순회인데, 우선 깊이 우선 순회를 보겠습니다.

 

• 깊이 우선 순회 (depth first traversal)
  • 중위 순회 (in-order traversal)
    • 순회 순서
      1. left subtree
      2. 자기 자신
      3. right subtree
  • 전위 순회 (pre-order traversal)
    • 순회 순서
    1. 자기 자신
    2. left subtree
    3. right subtree
  • 후위 순회 (post-order traversal)
    • 순회 순서
    1. left subtree
    2. right subtree
    3. 자기 자신

순회 순서에 따라 3가지 종류로 나뉩니다. 세가지 모두 코드로 구현 해보겠습니다.

 

class Node:
    
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None


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


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

    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 __init__(self, r):
        self.root = r


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


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

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

 

넓이 우선 순회도 살펴 보겠습니다.

 

넓이 우선 순회 (breadth first traversal)

• 원칙
  • 수준(level) 이 낮은 노드를 우선으로 방문
  • 같은 수준의 노드들 사이에는,
    • 부모 노드의 방문 순서에 따라 방문
    • 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문

재귀적 방법은 부적합하다.

 

한 노드를 방문했을 때

나중에 방문할 노드들을 기록해 두어야 한다.

→ 큐를 이용!

• 알고리즘 구현
  1. (초기화) traversal ← 빈 리스트, q ← 빈큐
  2. 빈 트리가 아니면, root node를 q에 추가 (enqueue)
  3. q 가 비어 있지 않은 동안
     1. node ← q에서 원소를 추출(dequeue)
     2. node 를 방문
     3. node 의 왼쪽, 오른쪽 자식(있으면) 들을 q에 추가
  4. q가 빈 큐가 되면 모든 노드 방문 완료

그렇다면 위의 알고리즘 대로 코드를 구현해 보겠습니다.

 

class ArrayQueue:
    
    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)

    def dequeue(self):
        return self.data.pop(0)

    def peek(self):
        return self.data[0]


class Node:

    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None


class BinaryTree:

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


    def bft(self):
        traversal=[]
        q=ArrayQueue()
        if self.root:
            q.enqueue(self.root)
        while not q.isEmpty():
            da=q.dequeue()
            traversal.append(da.data)
            if da.left:
                q.enqueue(da.left)
            if da.right:
                q.enqueue(da.right)
        
        return traversal

 

이때 헷갈렸던 점이 있는데, '큐' 라는 자료구조에는 Node형태의 데이터도 들어간다.
즉 리스트 라는 자료구조에는 Node형태의 데이터도 들어간다.
따라서 Node자체를 리스트에 넣었다가 꺼내 쓸 수 도 있으며 
Node 클래스에 저장 되어 있는 self.data, self.left 와 같은 변수 내용들도 전부 저장된다.