[1주차 - Day2] 어서와! 자료구조와 알고리즘은 처음이지? (2)

스택 (Stacks)

스택은 마지막에 넣었던 것부터 넣은 순서의 역순으로 꺼내지는 자료 구조입니다.

• size(): 현재 스택에 들어 있는 데이터 원소의 수를 구합니다.
• isEmpty(): 현재 스택이 비어 있는지를 판단합니다. (size() == 0?)
• push(x): 데이터 원소 x를 스택에 추가합니다.
• pop(): 스택에 가장 나중에 저장된 데이터 원소를 제거합니다. (또한, 반환합니다)
• peek(): 스택에 가장 나중에 저장된 데이터 원소를 참조 (반환), 그러나 제거하지 않습니다.

큐 (Queues)

큐는 데이터 원소를 한 줄로 늘어 세우는 자료 구조입니다.

• 선형구조: 데이터 원소를 한 줄로 늘어 세우는 자료 구조
• 선입선출 (FIFO; first-in first-out): 어느 시점에서 큐에 들어 있는 데이터 원소를 꺼내면 큐에 들어 있는 원소들 중 가장 먼저 넣었던 것이 꺼내집니다.
• 인큐 (enqueue): 데이터 원소를 큐에 넣는 동작입니다.
• 디큐 (dequeue): 큐로부터 데이터 원소를 꺼내는 동작입니다.

이진트리 (Binary Trees)

이진트리는 트리에 포함되는 모든 노드의 차수가 2 이하인 트리를 말합니다.

• size() - 현재 트리에 포함되어 있는 노드의 수를 구합니다.
• depth() - 현재 트리의 깊이 (또는 높이)를 구합니다.
• 중위 순회 (in-order traverasl): 왼쪽 서브트리를 순회한 뒤 노드 x를 방문, 그러고 나서 오른쪽 서브트리를 순회합니다.
• 전위 순회 (pre-order traversal): 노드 x를 방문한 후에 왼쪽 서브트리를 순회, 마지막으로 오른쪽 서브트리를 순회합니다.
• 후위 순회 (post-order traversal): 왼쪽 서브트리를 순회, 오른쪽 서브트리를 순회, 그러고 나서 마지막으로 노드 x를 방문합니다.

# (18-01) 이진트리의 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
        return max(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

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

def solution(x):
    return 0

# (18-02) 이진트리의 전위순회 연산 구현

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

# (18-03) 이진트리의 후위순회 연산 구현

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