3. Binary Tree - 파이썬 이진트리 공부하기

Binary Tree 란?

모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리.
하나의 노드는 최대 2개의 자식을 가질 수 있음.

높이가 h인 이진트리

노드의 최소 개수 : h+1개
노드의 최대 개수 : 2^(h+1) - 1 개

Node의 depth(깊이)와 height(높이)

노드의 depth란, 가장 아랫 노드인 leaf 노드와의 거리.
노드의 height란, 가장 상위 노드인 root 노드와의 거리.

---

이진 트리의 종류

Full Binary Tree

• 모든 레벨에 노드가 포화상태로 차 있는 이진 트리
• 최대의 노드 개수인 2^(h+1) -1개

Complete Binary Tree

• 높이가 h이고 노드 수가 n개일 때 Full Binary Tree의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리
• 노드의 left부터 채움

Skewed Binary Tree

• 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드 만을 가진 이진 트리

 

트리의 순회 (Tree Traversal)

가장 먼저 Node와 BinaryTree 클래스의 기본 골격을 생성한다.

class Node:
    def __init__(self, item):
        self.item = 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

    # 노드의 depth를 구함 (리프노드 - 노드 거리)
    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, root):
        self.root = root
        
    # 트리의 height를 구함 (루트노드 - 노드 거리)
    def height(self):
        l = self.root.left.height() if self.root.left else 0
        r = self.root.left.right() if self.root.right else 0
        return max(l, r) + 1

전위 순회 (Preorder)

    # 전위 순회
    def preorder_traverse(self):
        if self.root is not None:
            self.__preorder(self.root)

    def __preorder(self, cur):
        preorder_list = []
        preorder_list.append(cur.item)
        print(cur.item)
        if cur.left is not None:
            self.__preorder(cur.left)
        if cur.right is not None:
            self.__preorder(cur.right)

중위 순회 (Inorder)

    # 중위 순회
    def inorder_traverse(self):
        if self.root is not None:
            self.__inorder(self.root)

    def __inorder(self, cur):
        if cur.left is not None:
            self.__inorder(cur.left)

        inorder_list = []
        inorder_list.append(cur.item)
        print(cur.item)

        if cur.right is not None:
            self.__inorder(cur.right)

후위 순회 (Postorder)

    # 후위 순회
    def postorder_traverse(self):
        if self.root is not None:
            self.__postorder(self.root)

    def __postorder(self, cur):
        if cur.left is not None:
            self.__postorder(cur.left)

        if cur.right is not None:
            self.__postorder(cur.right)

        postorder_list=[]
        postorder_list.append(cur.item)
        print(cur.item)

 

Binary Search Tree

삽입 연산

    # 노드 삽입
    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self.insert_value(self.root, value)

    def insert_value(self, node, value):
        if value <= node.item:
            if node.left is None:
                node.left = Node(value)
            else:
                node.left = self.insert_value(node.left, value)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                node.right = self.insert_value(node.right, value)
        return node

 

탐색 연산

    # 노드 탐색
    def search(self, item):
        if self.root.item is None:
            return False
        else:
            return self.__search_node(self.root, item)

    def __search_node(self, cur, item):
        print(cur.item, item)
        if cur.item == item:
            return True
        else:
            if cur.item >= item:
                if cur.left is not None:
                    return self.__search_node(cur.left, item)
                else:
                    return False
            else:
                if cur.right is not None:
                    return self.__search_node(cur.right, item)
                else:
                    return False

 

삭제 연산

    # 노드 삭제
    def delete(self, value):
        self.root, deleted = self._delete_value(self.root, value)
        return deleted

    def _delete_value(self, node, value):
        if node is None:
            return node, False
        deleted = False
        # 해당 노드가 삭제할 노드일 경우
        if value == node.item:
            deleted = True
            # 삭제할 노드가 자식이 두개일 경우
            if node.left and node.right:
                # 오른쪽 서브 트리에서 가장 왼쪽에 있는 노드를 찾고 교체
                parent, child = node, node.right
                while child.left is not None:
                    parent, child = child, child.left
                child.left = node.left
                if parent != node:
                    parent.left = child.right
                    child.right = node.right
                node = child
            # 자식 노드가 하나일 경우 해당 노드와 교체
            elif node.left or node.right:
                node = node.left or node.right
            # 자식 노드가 없을 경우 그냥 삭제
            else:
                node = None
        elif value < node.item:
            node.left, deleted = self._delete_value(node.left, value)
        else:
            node.right, deleted = self._delete_value(node.right, value)
        return node, deleted