트리

트리 (tree)

트리는 계층적인 자료를 표현하는 데 이용되는 자료구조이다.

트리를 컴퓨터 메모리 상에서 표현하는 방법은 여러가지가 있을 수 있는데 서로 다른 개수의 자식 노드를 가지는 일반적인 트리는 구현이 복잡하다. 따라서 자식 노드의 개수가 2개로 고정된 이진트리가 가장 많이 사용된다.

이진 트리 (binary tree)

일반 트리와 다르게 모든 노드는 자식 노드의 개수가 2이하이고 서브 트리간에 순서가 존재한다.

이진 트리의 표현

이진 트리를 표현하는 방법에는 배열과 포인터 두가지가 있는데, 배열을 이용한 방법의 경우 기억 공간의 낭비가 심해 포인터를 이용한 방법이 주로 사용된다.

링크 표현법

소스코드

from queue import Queue 

class Node():
    def __init__(self, item):
        self.item = item
        self.llink = self.rlink = None

class BinaryTree():
    def __init__(self):
        self.root = None
        self.q = Queue()

    def is_empty(self):
        return self.root == None

    def insert(self, item):
        new = Node(item)
        if self.is_empty():
            self.root = new
            self.q.enqueue(new)
        else:
            parent = self.q.peek()
            if parent.llink == None:
                parent.llink = new    
                self.q.enqueue(new)
            elif parent.rlink == None:
                parent.rlink = new
                self.q.dequeue()
                self.q.enqueue(new)

완전 이진트리 형태를 띄도록 삽입하는 insert 함수를 큐를 이용해 구현하였다.

이진 트리의 순회

전위, 중위, 후위 순회

소스코드

    # 위 코드에 이어
    # ... 
    # 전위 순회
    def preorder(self, root):
        if root != None:
            print(root.item, end=' ')
            self.preorder(root.llink)
            self.preorder(root.rlink)

    # 중위 순회
    def inorder(self, root):
        if root != None:
            self.inorder(root.llink)
            print(root.item, end=' ')
            self.inorder(root.rlink)

    # 후위 순회
    def postorder(self, root):
        if root != None:
            self.postorder(root.llink)
            self.postorder(root.rlink)
            print(root.item, end=' ')

if __name__ == "__main__":
    b = BinaryTree()
    b.insert(15)
    b.insert(4)
    b.insert(20)
    b.insert(1)
    b.insert(16)
    b.insert(25)
    b.preorder(b.root)
    print(' ')
    b.inorder(b.root)
    print(' ')
    b.postorder(b.root)

출력

15 4 1 16 20 25
1 4 16 15 25 20
1 16 4 25 20 15

레벨 순회

소스코드

    # 위 코드에 이어
    # ...
    # 레벨 순회
    def level_order(self, root):
        q = Queue()
        q.enqueue(root)
        while not q.is_empty():
            child = q.dequeue()    
            print(child.item, end=' ')
            if child.llink != None:
                q.enqueue(child.llink)
            if child.rlink != None:
                q.enqueue(child.rlink)

if __name__ == "__main__":
    b = BinaryTree()
    b.insert('+')
    b.insert('*')
    b.insert('/')
    b.insert('A')
    b.insert('B')
    b.insert('C')
    b.insert('D')
    b.level_order(b.root)

출력

+ * / A B C D

이진 트리 순회의 응용

아래에 두 예제는 모두 후위순위를 사용한 계산 프로그램이다.

수식 트리 처리

소스코드

    # 위 코드에 이어
    # ...
    def evaluate(self, root):
        if root == None:
            return 0
        if root.llink == None and root.rlink == None:
            return root.item
        else:
            op1 = int(self.evaluate(root.llink))
            op2 = int(self.evaluate(root.rlink))

            if root.item == '+':
                return op1+op2
            elif root.item == '-':
                return op1-op2
            elif root.item == '*':
                return op1*op2
            elif root.item == '/':
                return op1/op2
        return 0

if __name__ == "__main__":
    b = BinaryTree()
    b.insert('*')
    b.insert('+')
    b.insert('+')
    b.insert('1')
    b.insert('4')
    b.insert('16')
    b.insert('25')
    b.level_order(b.root)
    print('')
    print(b.evaluate(b.root))

출력

* + + 1 4 16 25
205

디렉터리 용량 계산

소스코드

    # 위 소스코드에 이어
    # ...
    def calc_direc_size(self, root):
        left_size = right_size = 0
        if root != None:
            left_size = self.calc_direc_size(root.llink)
            right_size = self.calc_direc_size(root.rlink)
            return root.item + left_size + right_size
        return 0

if __name__ == "__main__":
    b = BinaryTree()
    b.insert(0)
    b.insert(50)
    b.insert(100)
    b.insert(200)
    b.insert(500)
    b.level_order(b.root)
    print('')
    print(b.calc_direc_size(b.root))

출력

0 50 100 200 500
850

이진 트리의 연산

노드의 개수

소스코드

    # 위 코드에 이어
    # ...
    def get_node_count(self, root):
        count = 0
        if root != None:
            count = 1 + self.get_node_count(root.llink) + self.get_node_count(root.rlink)
        return count

if __name__ == "__main__":
    b = BinaryTree()
    b.insert('+')
    b.insert('*')
    b.insert('/')
    b.insert('A')
    b.insert('B')
    b.insert('C')
    b.insert('D')
    print(b.get_node_count(b.root))

출력

7

단말 노드의 개수

소스코드

    # 위 코드에 이어
    # ...
    def get_leaf(self, root):
        count = 0
        if root != None:
            if root.llink == None and root.rlink == None:
                return 1
            else:
                count = self.get_leaf(root.llink) + self.get_leaf(root.rlink)

        return count        

    # 위 main 코드에 이어
    # ...
    print(b.get_leaf(b.root))

출력

4

트리의 높이

소스코드

    # 위 코드에 이어
    # ...
    def get_height(self, root):
        height = 0
        if root != None:
            height = 1 + max(self.get_height(root.llink), self.get_height(root.rlink))

        return height

    # 위 main 코드에 이어
    # ...
    print(b.get_height(b.root))

출력

3

이진 탐색 트리 (binary search tree)

이진 트리 기반의 탐색을 위한 자료구조이다.

왼쪽 서브트리의 키는 루트보다 작고 오른쪽 서브트리의 키는 루트보다 크며 모든 노드의 키는 유일해야 한다.

탐색, 삽입, 삭제

소스코드

class Node():
    def __init__(self, item):
        self.item = item
        self.llink = self.rlink = None

class BinarySearchTree():
    def __init__(self):
        self.root = None

    def is_empty(self):
        return self.root == None

    def search(self, root, item):
        if root == None:
            return None

        if item < root.item:
            return self.search(root.llink, item)
        elif item > root.item:
            return self.search(root.rlink, item)
        else:
            return root.item

    def insert_node(self, item):
        cnt = self.root # 노드가 삽입될 자리
        parent = None
        while cnt != None:
            if item == cnt.item:
                return None
            parent = cnt
            if item < cnt.item:
                cnt = cnt.llink
            elif item > cnt.item:
                cnt = cnt.rlink    

        new = Node(item)
        if self.root == None:
            self.root = new    
        else:    
            if item < parent.item:
                parent.llink = new
            else:
                parent.rlink = new

    def delete_node(self, item):
        cnt = self.root # 삭제하려는 노드
        parent = None
        while cnt != None:
            if item == cnt.item:
                break
            parent = cnt
            if item < cnt.item:
                cnt = cnt.llink
            elif item > cnt.item:
                cnt = cnt.rlink

        # 찾으려는 노드가 없을 경우
        if cnt == None:
            return None

        # 단말 노드인 경우
        if cnt.llink == None and cnt.rlink == None:
            # root 노드일 경우
            if parent == None:
                root = None
            else:
                if item < parent.item:
                    parent.llink = None
                else:
                    parent.rlink = None

        # 두개의 서브트리를 가지고 있는 경우
        elif cnt.llink != None and cnt.rlink != None:        
            # 오른쪽 서브트리의 맨 왼쪽 자식을 후계자로 설정
            succ_p = cnt # 후계자 노드의 부모
            succ = cnt.rlink # 후계자 노드

            while succ.llink != None:
                succ_p = succ
                succ = succ.llink

            # 후계자에게 자식이 있다면 후계자의 부모와 연결
            if succ_p.llink == succ:
                succ_p.llink = succ.rlink
            else:
                succ_p.rlink = succ.rlink

            cnt.item = succ.item

        # 한쪽 서브트리만을 가지고 있는 경우
        else:
            # 한쪽 서브트리가 어느쪽인지 확인
            if cnt.llink != None:
                child = cnt.llink
            else:
                child = cnt.rlink

            # root 노드일 경우
            if parent == None:
                root = child    
            else:
                parent = child

    def preorder(self, root):
        if root != None:
            print(root.item, end=' ')
            self.preorder(root.llink)
            self.preorder(root.rlink)

if __name__ == "__main__":
    b = BinarySearchTree()
    b.insert_node(35)
    b.insert_node(18)
    b.insert_node(7)
    b.insert_node(26)
    b.insert_node(3)
    b.insert_node(12)
    b.insert_node(22)
    b.insert_node(30)
    b.insert_node(68)
    b.insert_node(99)
    b.insert_node(24)

    print(b.search(b.root, 18))
    b.preorder(b.root)
    b.delete_node(18)
    print('')
    b.preorder(b.root)
    print('')
    print(b.search(b.root, 18))

출력

18
35 18 7 3 12 26 22 24 30 68 99
35 22 7 3 12 26 24 30 68 99
None

참고

• [DataStructure] 완전이진트리의 삽입과 합계 - 자스민