[Data Structure] Binary Tree

1. Binary Tree란?

<Binary Tree 구조>

위 사진은 Binary Tree의 구조를 나타내는 사진이다. 앞서 설명한 General Tree와 다른 점이 보이는가? 그건 바로 child가 최대 2명이라는 거다. 그럼 여기서 의문이 든다. child를 여러 명으로 생성하는 General Tree를 쓰지 왜 child가 두 명으로 제한되는 Binary Tree를 쓰는 것인가? 그것은 바로 데이터를 찾을 때 유용하기 때문이다. 

 예를들어, 리스트에 들어있는 숫자 중에서 내가 원하는 숫자를 찾는다고 가정하자. 이럴 경우, 처음부터 찾아가기 시작하여 시간복잡도가 크다. 만약 이 시간 복잡도를 줄이기 위해서는 어떻게 해야 할까? 그건 바로 규칙을 정해 수를 나누는 거다. 

이 과정에서 Binary Tree를 쓰면 시간복잡도가 O(log(n))으로 줄어들어 효율적으로 찾을 수 있다. 

 

따라서, Binary Tree는 최소 최대 또는 내가 원하는 수를 찾을 때 쓸 수 있겠다는 생각이 들었다.

class BinarySearchTree:
    def __init__(self,data):
        self.data = data 
        self.left = None 
        self.right = None 

    def add_child(self,data):
        if data == self.data:
            return 
        
        if data < self.data:
            if self.left:
                self.left.add_child(data)
            else:
                self.left = BinarySearchTree(data) 
            
        else:
            if self.right:
                self.right.add_child(data)
            else:
                self.right = BinarySearchTree(data)
    
    def search(self,val):
        if self.data == val:
            return True 
        
        if val < self.data:
            if self.left:
                return self.left.search(val)
            else:
                return False 
            
        if val > self.data:
            if self.right:
                return self.right.search(val)
            else:
                return False 



    def in_order_traversal(self):
        elements = []
        if self.left:
            elements +=self.left.in_order_traversal()
        elements.append(self.data)
        
        if self.right:
            elements += self.right.in_order_traversal()
        return elements 
    
    def find_min(self):
        if self.left is None:
            return self.data 
        return self.left.find_min() 
            
    def find_max(self):
        if self.right is None:
            return self.data 
        return self.right.find_max()
    
    def calculate_sum(self):
        elements = self.in_order_traversal()
        sum_ele = sum(elements)
        return sum_ele
    
    def post_order_traversal(self):
        elements = []
        if self.left:
            elements += self.left.post_order_traversal()
        if self.right:
            elements += self.right.post_order_traversal()
        elements.append(self.data)
        return elements 
    
    def pre_order_traversal(self):
        elements = [self.data]
        if self.left:
            elements.extend(self.left.pre_order_traversal()) 
        if self.right:
            elements.extend(self.right.pre_order_traversal())
        return elements