[자료구조] 트리(Tree)

이미지 출처 : https://python.plainenglish.io/data-structures-tree-29c825760095

- Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조

- 이진트리 : 노드의 최대 Branch가 2인 트리

- 이진탐색트리(Binary Search Tree, BST) : 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가진다.

 

#코드

class Node:
    def __init__ (self, value):
        self.value = value
        self.left  = None
        self.right = None
 
class NodeMgmt:
    def __init__(self, head):
        self.head = head
    
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value: # 찾고자하는 value값이 작은 경우 : 왼쪽 
                if self.current_node.left != None: # 왼쪽에 자식이 있을 경우
                    self.current_node = self.current_node.left # 왼쪽으로 계속 이동한다.
                else: # 자식이 없을 경우
                    self.current_node.left = Node(value) #노드생성
                    break
            else: # 찾고자하는 value값이 큰 경우 : 오른쪽
                if self.current_node.right != None: # 오른쪽에 자식이 있을 경우
                    self.current_node = self.current_node.right
                else: # 자식이 없을 경우
                    self.current_node.right = Node(value) #노드생성
                    break
 
    def search(self, value):
        self.current_node = self.head
        while self.current_node: # self.head에 값이 있을 경우
            if self.current_node.value == value: # 찾고자하는 값과 일치할 경우
                return value
            elif self.current_node.value > value: # 왼쪽 탐색
                self.current_node = self.current_node.left
            else: # 오른쪽 탐색
                self.current_node = self.current_node.right
        return False
 
    '''
    설계
    1) Leaf Node삭제 : 해당 노드를 삭제하고 해당 노드의 부모노드가 가르키는 값을 None으로 초기화
    2) Child Node가 하나인 Node삭제 : 해당 노드를 삭제하고 해당 노드의 브랜치가 삭제 노드의 자식 노드를 가르킨다.
    3) Child Node가 두개인 Node삭제 : 
       - 삭제할 노드의 오른쪽 자식 중, 가장 작은 값을 삭제할 노드의 부모 노드가 가르키도록 한다.
                                            or 
       - 삭제할 노드의 왼쪽 자식 중, 가장 큰 값을 삭제할 노드의 부모 노드가 가크리도록 한다.
 
    전략
    1. 삭제할 노드의 오른쪽 자식 선택
    2. 오른쪽 자식의 가장 왼쪽에 있는 노드를 선택
    3. 해당 노드를 삭제할 노드의 부모 노드의 왼쪽 브랜치가 가르키게함.
    4. 해당 노드의 왼쪽 브랜치가 삭제할 노드의 왼쪽 자식노드를 가르키게함.
    5. 해당 노드의 오른쪽 브랜치가 삭제할 노드의 오른쪽 자식노드를 가르키게함.
    6. 만약 해당 노드의 오른쪽 자식노드가 있을 경우, 
    해당 노드의 부모노드의 왼쪽 브랜치가 해당노드 오른쪽 자식노드를 가르키게함.    
    '''
    def delete(self, value):
        searched = False # 삭제할 노드가 없는 경우도 처리해야함.
        # 삭제할 노드 탐색
        self.current_node = self.head
        self.parent_node  = self.head
        while self.current_node: 
            if self.current_node.value == value:
                searched = True
                break
            elif value < self.current_node.value:
                self.parent_node = self.current_node
                self.current_node = self.current_node.left
            else:
                self.parent_node = self.current_node
                self.current_node = self.current_node.right
        if searched == False:  
            return False # 삭제하고자 하는 값이 없는 경우 종료한다.
        # case 1 : 삭제할 노드가 leaf node인 경우 
        if self.current_node.left == None and self.current_node.right == None:
            if value < self.parent_node.value:
                self.parent_node.left = None
            else:
                self.parent_node.right = None
            del self.current_node
        # case 2 : 삭제할 노드가 child node를 한 개 가지고 있는 경우
        if self.current_node.left != None and self.current_node.right == None: # 왼쪽 한 개
            if value < self.parent_node.value:
                self.parent_node.left = self.current_node.left
            else:
                self.parent_node.right = self.current_node.left
        elif self.current_node.left == None and self.current_node.right != None: # 오른쪽 한 개
            if value < self.parent_node.value:
                self.parent_node.left = self.current_node.right
            else:
                self.parent_node.right = self.current_node.right
        # case 3 : 삭제할 노드가 자식노드를 두 개 가지고 있는 경우
        if self.current_node.left != None and self.current_node.right != None:
            # case 3-1 : 삭제할 노드가 부모노드의 왼쪽
            if value < self.parent_node.value: 
                self.change_node = self.current_node.right  
                self.change_node_parent = self.current_node.right
                while self.change_node.left:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                # case 3-1-1 : 삭제할 노드가 부모 노드의 왼쪽에 있고, 
                #              삭제할 노드의 오른쪽 자식 중 가장 작은 값을 가진 노드의 오른쪽 자식노드가 있을 때        
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                # case 3-1-2 : 삭제할 노드가 부모노드의 왼쪽에 있고, 
                #              삭제할 노드의 오른쪽 자식 중 가장 작은 값을 가진 노드의 자식이 없을 때
                else:
                    self.change_node_parent.left = None
                ###### 실질적 교체
                self.parent_node.left = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right
            # case 3-2 : 삭제할 노드가 부모노드의 오른쪽
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left                
                # case 3-2-1 : 삭제할 노드가 부모 노드의 오른쪽에 있고, 
                #              삭제할 노드의 오른쪽 자식 중 가장 작은 값을 가진 노드의 자식 노드가 있을 때
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right 
                # case 3-2-2 : 삭제할 노드가 부모 노드의 오른쪽에 있고, 
                #              삭제할 노드의 오른쪽 자식 중 가장 작은 값을 가진 노드의 자식 노드가 없을 때
                else:
                    self.change_node_parent.left = None
                ###### 실질적 교체
                self.parent_node.right = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right
        return True
                
        
 
if __name__ == "__main__":
    head = Node(1)
    bst =NodeMgmt(head)
    bst.insert(2)
    bst.insert(3)
    res = bst.search(2)
    if res != False:        
        print(res)
    else:
        print('찾고자하는 값이 없습니다.')
 
    res = bst.delete(2)
    print(res)

# 시간복잡도 : O(logN)

 

# 전위/중위/후위 순회(복습)

import sys 
 
def preorder(x):
  # x를 루트로 하는 서브트리를 전위순회 하여 출력하는 함수.
  # 기저조건 : 노드의 자식 노드가 없을 때
  if myTree[x][0] == -1 and myTree[x][1] == -1:
    print(x, end=' ')
  else:
    # Root -> Left -> Right
    print(x, end=' ')
    preorder(myTree[x][0])
    preorder(myTree[x][1])
 
def inorder(x):
  if myTree[x][0] == -1 and myTree[x][1] == -1:
    print(x, end=' ')
  else:
    inorder(myTree[x][0])
    print(x, end=' ')
    inorder(myTree[x][1])
    
def postorder(x):
  if myTree[x][0] == -1 and myTree[x][1] == -1:
    print(x, end=' ')
  else:
    postorder(myTree[x][0])
    postorder(myTree[x][1])
    print(x, end=' ')
  
 
if __name__ == "__main__":
  input = sys.stdin.readline
  
  n = int(input())
  # myTree[i] = 노드 i의 정보를 담고 있다.
  # myTree[i][0] = 노드 i의 왼쪽 노드 번호.
  # myTree[i][1] = 노드 i의 오른쪽 노드 번호.
  
  myTree = [[] for _ in range(n+1)]
  
  for _ in range(n):
    a, b, c = map(int, input().split())
    myTree[a].append(b) 
    myTree[a].append(c)
  
  
  preorder(1)
  print()
  inorder(1)
  print()
  postorder(1)

입력
5
1 2 3
2 4 5
3 -1 -1
4 -1 -1
5 -1 -1

출력
1 2 4 5 3 
4 2 5 1 3 
4 5 2 3 1 

 

# 문제

https://ttolkist.tistory.com/155

트리 순회 결과 출력하기