트리 순회(Tree traversal)

2019-07-08

순회

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

Queue 계열의 알고리즘

BFS(Breadth First Search) : 너비 우선 탐색

레벨 순서 순회(levelorder traversal)

root를 시작으로 다음 레벨 왼쪽부터 방문

# python Queue module 이용
from queue import Queue

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

def levelorder(cur):
    q = Queue()

    q.put(cur)

    while not q.empty():
        cur = q.get()
        print(cur.data, end = " ")

        if cur.left:
            q.put(cur.left)
        if cur.right:
            q.put(cur.right)


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

    levelorder(n1)

BST(Binary Search Tree)

insert, search, delete 모두 O(log(n))
최악의 경우 모두 O(n)
데이터가 정렬되어 있다.

insert를 할 때 반드시 empty node에 들어가게 되어있다.

class TreeNode:
    def __init__(self, key=None):
        self.__key = key
        self.__left = None
        self.__right = None

    # getter
    @property
    def key(self):
        return self.__key

    # setter
    @key.setter
    def key(self, key):
        self.__key = key

    @property
    def left(self):
        return self.__left

    @left.setter
    def left(self, left):
        self.__left = left

    @property
    def right(self):
        return self.__right

    @right.setter
    def right(self, right):
        self.__right = right

class BST:
    def __init__(self):
        self.__root = None

    @property
    def root(self):
        return self.__root

    def preorder(self, cur):
        if not cur:
            return

        print(cur.key, end = " ")
        self.preorder(cur.left)
        self.preorder(cur.right)
    
    def insert(self, key):
        new_node = TreeNode(key)

        cur = self.__root

        if not cur:
            self.__root = new_node
            return
        
        while True:
            parent = cur
            if key < cur.key:
                cur = cur.left
                if not cur:
                    parent.left = new_node
                    return
            else:
                cur = cur.right
                if not cur:
                    parent.right = new_node
                    return
    
    def search(self, target):
        # 함수를 구현할 때는 예외사항을 모두 생각하면 만들어야 한다.
        # root가 존재하지 않을 경우, cur가 None이므로 while 문이 돌지 않고 바로 빠져나가게 된다.
        cur = self.__root

        while cur:
            if cur.key == target:
                return cur
            
            elif cur.key > target:
                cur = cur.left

            else:
                cur = cur.right
            
        return None
    
    # 1. 리프 노드일 때
    # 2. 자식이 하나일 때 - 왼쪽, 오른쪽
    # 3. 자식이 둘일 때
    def delete(self, target):
        self.__root = self.__delete_recursion(self.__root, target)

    # 재귀 함수
    # 자료구조에서 데이터를 빼고 반환하지 않는다. --> delelte
    # 자료구조에서 데이터를 빼고 사용자에게 반환해준다. --> remove
    def __delete_recursion(self, cur, target):
        # base case
        if not cur:
            return None
        elif target < cur.key:
            cur.left = self.__delete_recursion(cur.left, target)
        elif target > cur.key:
            cur.right = self.__delete_recursion(cur.right, target)
        # target == cur.key
        else:
            # 1. 삭제 노드가 리프 노드인 경우
            if not cur.left and not cur.right:
                cur = None

            # 2. 삭제 노드의 자식이 하나일 때
            # 왼쪽 자식이 있는 경우
            elif not cur.right:
                cur = cur.left

            # 오른쪽 자식이 있는 경우
            elif not cur.left:
                cur = cur.right

            # 3. 삭제 노드의 자식이 둘일 때
            # - 왼쪽 서브 트리에서 가장 큰 수
            # - 오른쪽 서브 트리에서 가장 작은 수
            else:
                # 대체 노드를 찾는다
                rep = cur.left
                while rep.right:
                    rep = rep.right
                # 삭제 노드와 대체 노드의 키를 교환
                cur.key, rep.key = rep.key, cur.key

                cur.left = self.__delete_recursion(cur.left, rep.key)

        return cur

# test code
if __name__ == "__main__":
    bst = BST()

    bst.insert(6)
    bst.insert(3)
    bst.insert(8)
    bst.insert(2)
    bst.insert(4)
    bst.insert(10)
    bst.insert(9)
    bst.insert(11)

    bst.preorder(bst.root)
    print()
    bst.insert(5)
    bst.preorder(bst.root)

    print()

    ret = bst.search(13)
    if ret:
        print(f"{ret.key} is found.")
    else:
        print("No such data.")

    # 삭제노드가 리프 노드일 때
    # bst.delete(9)
    # bst.delete(8)
    bst.delete(6)

    bst.preorder(bst.root)

지눅쿠의 개발 블로그

StudyData Structure

트리 순회(Tree traversal)

순회

BST(Binary Search Tree)