원형 큐(Circular Queue)와 트리 순회(Tree traversal)

2019-07-04

원형 큐(Circular Queue)

선형 큐의 문제점을 보완하기 위한 자료구조
크기가 정해져 있는 배열(list)
head, tail이 존재
empty : head == tail
full : tail + 1 == head

tail은 마지막 데이터의 다음을 가리킨다.

class CQueue:
    MAXSIZE = 10
    
    def __init__(self):
        self.__container = [None for _ in range(CQueue.MAXSIZE)]
        self.__head = 0
        self.__tail = 0

    def is_empty(self):
        if self.__head == self.__tail:
            return True
        return False

    def is_full(self):
        next = self.__step_forward(self.__tail)
        if next == self.__head:
            return True
        return False

    def enqueue(self, data):
        if self.is_full():
            raise Exception("The queue is full.")
        self.__container[self.__tail] = data
        # tail은 마지막 데이터의 다음을 가리킨다.
        self.__tail = self.__step_forward(self.__tail)

    def dequeue(self):
        if self.is_empty():
            raise Exception("The queue is empty.")
        
        ret = self.__container[self.__head]
        self.__head = self.__step_forward(self.__head)
        return ret

    def peek(self):
        if self.is_empty():
            raise Exception("The queue is empty.")

        return self.__container[self.__head]

    # 편의 함수
    def __step_forward(self, x):
        x += 1
        if x >= CQueue.MAXSIZE:
            x = 0
        return x

# test code
if __name__ == "__main__":
    cq = CQueue()

    for i in range(8):
        cq.enqueue(i)

    for i in range(5):
        print(cq.dequeue(), end=" ")

    print()

    for i in range(8, 14):
        cq.enqueue(i)

    while not cq.is_empty():
        print(cq.dequeue(), end=" ")

    print()

    for i in range(10):
        print(cq._CQueue__container[i], end="  ")

순회

재방문을 허용하지 않고 트리를 구성하는 모든 노드에 다해서 반드시 한번씩 방문하는 것

Stack 계열의 알고리즘

DFS(Depth First Search) : 깊이 우선 탐색
재귀(recursion)와 반복문, stack 자료구조를 통한 구현 - stack frame
전위 순회(preorder traversal)
- root -> 왼쪽 서브 트리 -> 오른쪽 서브 트리
중위 순회(inorder traversal)
- 왼쪽 서브 트리 -> root -> 오른쪽 서브 트리

후위 순회(postorder traversal)

왼쪽 서브 트리 -> 오른쪽 서브 트리 -> root

class Stack:
    def __init__(self):
        self.container = list()

    def is_empty(self):
        if not self.container:
            return True
        else:
            return False

    # 래핑 함수 : 기존에 있던 함수의 기능을 재정의해서 사용하는 함수
    def push(self, data):
        self.container.append(data)

    def pop(self):
        return self.container.pop()

    def peek(self):
        return self.container[-1]

# traversal(순회)
# 재방문없이 어떤 자료구조의 모든 데이터(노드)를 방문하는 것
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# 전위 순회
def preorder(node):
    # base case
    if not node:
        return
    
    # 방문했다는 표시를 print로 함
    print(node.data, end=' ')
    # 왼쪽 자식
    preorder(node.left)
    # 오른쪽 자식
    preorder(node.right)

# 중위 순회
def inorder(node):
    # base case
    if not node:
        return

    inorder(node.left)
    print(node.data, end=' ')
    inorder(node.right)
    
# 후위 순회
def postorder(node):
    # base case
    if not node:
        return

    postorder(node.left)
    postorder(node.right)
    print(node.data, end=' ')

# stack을 이용한 전위 순회
def iter_preorder(cur):
    s = Stack()

    while True:
        while cur:
            # 방문은 print로 표현
            print(cur.data, end=" ")
            s.push(cur)
            cur = cur.left
        if s.is_empty():
            break

        cur = s.pop()
        cur = cur.right

# stack을 이용한 중위 순회
def iter_inorder(cur):
    s = Stack()

    while True:
        while cur:
            s.push(cur)
            cur = cur.left

        if s.is_empty():
            break

        cur = s.pop()
        # 방문은 print로 표현
        print(cur.data, end=" ")
        cur = cur.right

# stack을 이용한 후위 순회
def iter_postorder(cur):
    s1 = Stack()
    s2 = Stack()

    s1.push(cur)

    while not s1.is_empty():
        cur = s1.pop()
        if cur.left:
            s1.push(cur.left)
        if cur.right:
            s1.push(cur.right)
        s2.push(cur)
    
    while not s2.is_empty():
        cur = s2.pop()
        # 방문은 print로 표현
        print(cur.data, end = " ")

# test code
if __name__ == "__main__":
    n1 = TreeNode(1)
    n2 = TreeNode(2)
    n3 = TreeNode(3)
    n4 = TreeNode(4)
    n5 = TreeNode(5)
    n6 = TreeNode(6)
    n7 = TreeNode(7)

    n1.left = n2
    n1.right = n3
    n2.left = n4
    n2.right = n5
    n3.left = n6
    n3.right = n7

    # preorder(n1)
    # print("")
    # inorder(n1)
    # print("")
    # postorder(n1)

    iter_preorder(n1)
    print("")
    iter_inorder(n1)
    print("")
    iter_postorder(n1)

지눅쿠의 개발 블로그

StudyData Structure

원형 큐(Circular Queue)와 트리 순회(Tree traversal)

원형 큐(Circular Queue)

순회