이진 트리(Binary Trees)

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

• 연산의 정의
  • size() - 현재 트리에 포함되어 있는 노드의 수를 구함
  • depth() - 현재 트리의 깊이(또는 높이: height)를 구함
  • 순회(traversal)
• 이진 트리의 구현 - 노드(Node)

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

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

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

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

• 깊이 우선 순회(depth first traversal)
  • 중위 순회
  • 전위 순회
  • 후위 순회
• 중위 순회 구현(In-order-Traversal)

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

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

• 넓이 우선 순회(breadth first traversal)

 

이진 트리의 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


def solution(x):
    return 0

 

이진트리의 전위순회 연산 구현

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

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 solution(x):
    return 0

 

이진 트리의 후위순회 연산 구현

 

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 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 postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []


def solution(x):
    return 0

이진 트리 - 넓이 우선 순회(breadth first traversal)

---

원칙

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

-> 재귀적 방법이 적절할까?

적절하지 않다. 재귀적 방법을 적용하면 수준이 깊은 노드부터 우선 탐색하게 되는 성질때문에 같은 수준의 노드들을 순서대로 먼저 방문해야 하는 너비 우선 탐색 특성상 적합하지 않은 것 아닐까?

 

• 한 노드를 방문했을 때,
  • 나중에 방문할 노드들을 순서대로 기록해 두어야함

-> 큐(queue)를 이용하면 어떨까? 선입선출 자료구조 방식이니까 먼저 방문해야 할 노드들부터 할 수 있을것 같다.

 

넓이 우선 순회 알고리즘 설계

class BinaryTree:
	def bft(self):
    		pass

 

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 q.size() != 0:
            now = q.dequeue()
            traversal.append(now.data)
            if now.left:
                q.enqueue(now.left)
            if now.right:
                q.enqueue(now.right)
        return traversal


def solution(x):
    return 0