2주차 자료구조 - 이진트리 삽입,탐색,삭제,순회

class를 이용해서 트리랑 트리순회를 구현을 하던데 도저히 혼자 못할 거 같아서 참고했다,,,ㅜㅜ

www.fun-coding.org/Chapter10-tree.html  완전 잘 정리해놓으셨다. 

그래도 삭제할때 양쪽 다 자식노드가 존재하는 경우가 너무 어렵고, 이해가 안돼서 직접 그려서 이해했다...

 

1) delete #4 : 양쪽 자식이 다 존재하는 경우 , 최솟값 노드의 오른쪽 자식이 존재하는 경우 

 

2) delete #4 : 양쪽 자식이 다 존재하는 경우 , 최솟값 노드의 자식이 존재하지 않는 경우 

 

# 전체 코드 구현 

class Node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
    def __str__(self):
        return str(self.data)

class tree:
    def __init__(self,data):
        self.root = Node(data) 
        #left - 맨처음 루트값 - right로 이뤄진 노드를 불러옴 
     
    def insert(self, data):
        # 맨 처음 루트값부터 시작
        self.current_node = self.root
        while True:
            # 삽입할 값이 현재값보다 작디면 오른쪽 노드로 넘어간다
            if data < self.current_node.data:
                # 왼쪽 노드가 이미 차있다면 왼쪽 노드가 비교대상인 현재노드로 바뀜 
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                #만약 왼쪽 노드에 아무것도 없다면 그 자리로 쏙 
                else:
                    self.current_node.left = Node(data)
                    break
            else:
                # 오른쪽 노드가 이미 차있다면 오른쪽 노드가 비교대상인 현재노드로 바뀜 
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                #만약 오른쪽 노드에 아무것도 없다면 그 자리로 쏙 
                else:
                    self.current_node.right = Node(data)
                    break
                    
    def search(self,data) : 
        self.cur = self.root #Node(data)
#        if not  self.cur : return False
        # 더이상 넘어갈 노드가 없는데 아직까지 true를 반환안했으면 여기 없는 data 
        while self.cur:
            if self.cur.data == data:
                return True
            elif self.cur.data > data:
                 self.cur = self.cur.left
            else:
                 self.cur = self.cur.right
        return False 
        
    
    def delete(self, data):
        # 삭제할 값이 우선 트리에 있는 값인지 확인한다.
        check = self.search(data)
        if not check:    
            return False
       
        self.cur = self.root;
        self.parents = self.cur;
        
      # 삭제할 노드까지 가기
        while self.cur:
            if data == self.cur.data:
                break
            elif data > self.cur.data :
                self.parents= self.cur
                self.cur = self.cur.right 
            else :
                self.parents= self.cur
                self.cur = self.cur.left
            
            
    # 1. 자식노드가 없는 상황
        if self.cur.left == None and self.cur.right == None :
            # 부모노드보다 오른쪽에 있다면 부모의 오른쪽 노드 삭제
            if data > self.parents.data : 
                self.parents.right = None
            # 부모노드보다 왼쪽에 있다면 부모의 왼쪽 노드 삭제
            else :
                self.parents.left = None
        
     # 2. 자식 노드가 왼쪽만 있는 상황 
        elif self.cur.left and not self.cur.right:
            if self.parents.data > self.cur.data:
                   # 부모보다 왼쪽의 데이터라면 자식노드의 왼쪽노드가 부모노드의 왼쪽노드가 됨
                self.parents.left = self.cur.left  
            else :
                    # 부모보다 오른쪽의 데이터라면 자식노드의 왼쪽노드가 부모노드의 오른쪽노드가 됨
                self.parents.right = self.cur.left  
                        
    # 3.자식 노드가 오른쪽만 있는 상황       
        elif  self.cur.right and not self.cur.left:
            if self.parents.data > self.cur.data:
                # 부모보다 왼쪽의 데이터라면 자식노드의 오른쪽노드가 부모노드의 왼쪽노드가 됨
                self.parents.left = self.cur.right  
            else :
                # 부모보다 오른쪽의 데이터라면 자식노드의 오른쪽노드가 부모노드의 오른쪽노드가 됨
                self.parents.right = self.cur.right  
            
    #4. 자식 노드가 양쪽 다 있는 상황
        else:
            # 최솟값 노드와 그 부모노드 
            self.temp = self.cur.right
            self.parents_temp= self.temp
            
            # 이렇게 오른쪽노드의 왼쪽자식들 중 가장 작은 값을 찾는다.
            while self.temp.left:
                    self.parents_temp = self.temp
                    self.temp = self.temp.left
            # 왼쪽에서 가장 작은 값을 찾는 거라서 최솟값 노드의 왼쪽 노드는 존재하지 않는다.
            # 최솟값 노드의 오른쪽 노드가 존재한다면 
            if self.temp.right :
                # 최솟값 노드의 부모노드의 왼쪽노드가 최솟값 노드의 오른쪽으로 대체됨 
                self.parents_temp.left = self.temp.right
                # 최솟값이 자식노드를 가지고 있지 않다면 최솟값의 부모노드의 왼쪽 삭제 .
            else :
                 self.parents_temp.left = None
            
            # 삭제할 값이 부모노드보다 왼쪽이라면 부모노드의 왼쪽노드가 바뀜 
            if data < self.parents.data : 
                self.parents.left = self.temp
                self.temp.right = self.cur.right
                self.temp.left = self.cur.left
                
            # 삭제할 값이 부모노드보다 오른쪽이라면 부모노드의 쪽노드가 바뀜 
            else:
                self.parents.right = self.temp
                self.temp.right = self.cur.right
                self.temp.left = self.cur.left
                
    def pre_order_traversal(self):
        def _pre_order_traversal(root):
            if root is None:
                pass
            else:
                 # 전위순회 : 뿌리 -> 왼쪽 -> 오른쪽 
                print(root.data)
                _pre_order_traversal(root.left)
                _pre_order_traversal(root.right)
        _pre_order_traversal(self.root)
                         
    def in_order_traversal(self):
        def _in_order_traversal(root):
            if root is None:
                pass
            else:
                # 중위순회 :왼쪽 -> 뿌리 ->오른쪽 
                _in_order_traversal(root.left)
                print(root.data)
                _in_order_traversal(root.right)
        _in_order_traversal(self.root)
        
    def post_order_traversal(self):
        def _post_order_traversal(root):
            if root is None:
                pass
            else:
                # 후위순회 :왼쪽  ->오른쪽 -> 뿌리
                _post_order_traversal(root.left)
                _post_order_traversal(root.right)
                print(root.data)
        _post_order_traversal(self.root)

진짜 너무너무너무너무 어렵다.

class 잘 쓰고 싶다 나도 힝 ㅜ