[프로그래머스 강의] 18강 이진 트리(Binary Tree)

---

'어서와! 자료구조와 알고리즘은 처음이지?'

---

 

이진 트리(Binary Tree)

연산의 정의

1. size() - 현재 트리에 포함되어 있는 노드의 수를 구한다.

2. depth() - 현재 트리의 깊이 (또는 높이, height)를 구한다.

3. 순회(traversal)

 

이진 트리의 구현 - 노드(Node)

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

 

이진 트리의 구현 - 트리(Tree)

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

 

이진 트리의 구현 - size()

재귀적인 방법으로 쉽게 구할 수 있다.

LEAF 노드에 A는 오타입니다... ! A -> F

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

 

이진 트리의 구현 - depth()

이진 트리의 순회(Traversal)

1.  깊이 우선 순회(depth first traversal)

     ✔ 중위 순회(in-order traversal)

     ✔ 전위 순회(pre-order traversal)

     ✔ 후위 순회(post-order traversal)

2.  넓이 우선 순회(breadth first traversal)

중위 순회(In-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 []

 

전위 순회(Pre-order Traversal)

 

후위 순회(Post-order Traversal)

 

[ 문1. 이진트리의 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

 

[ 문2. 이진트리 후위순회 구현 ]

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

 

[ 문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



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