🌞 Tree Search 문제

Tree: Preorder Traversal
Tree: Inorder Traversal
Tree: Postorder Traversal
Tree: Levelorder Traversal

🚊 문제 공통 사항

🚢 이진탐색트리 클래스

# 1. Node 클래스 선언
class Node:
    def __init__(self, info): 
    	# Node의 데이터 = info
        self.info = info
        # Node의 왼쪽 = None
        self.left = None  
        # Node의 오른쪽 = None
        self.right = None 
        # Node의 level = None
        self.level = None 

	# init에서 규정한 클래스 자체 내용을 출력
    def __str__(self):
        return str(self.info) 

# 이진탐색트리 클래스 선언
class BinarySearchTree:
    def __init__(self):
    	# root 노드를 None으로 선언
        self.root = None
	
    # 이진탐색트리에 데이터 삽입
    
    def create(self, val):  
    	# root 노드가 없으면
        if self.root == None:
        	# val 값을 갖는 노드를 생성하여 root 노드에 할당하고 끝냄.
            self.root = Node(val)
        #  root 노드가 있으면
        else:
        	# 현재 노드를 root 노드로 지정
            current = self.root
         	# 계속 반복
            #   삽입할 위치를 먼저 찾고, 완료되면 해당 노드의 데이터를 val로 지정하는 방식
            while True:
            	# 삽입하려는 데이터 값이 현재 노드의 데이터 값보다 작다면 → 왼쪽으로 내려가서 삽입할 위치를 찾음.
                if val < current.info:
                	# 현재 노드의 왼쪽 노드가 있으면
                    if current.left:
                    	# 삽입할 탐색 위치를 현재 노드의 왼쪽 노드로 변경
                        current = current.left
                    # 현재 노드의 왼쪽 노드가 없다면
                    else:
                    	# val 값을 갖는 노드를 생성하여 현재 노드의 왼쪽 노드에 할당.
                        current.left = Node(val)
                        # 데이터 삽입을 끝냈으니 반복문 종료시키고 끝냄.
                        break
                # 삽입하려는 데이터 값이 현재 노드의 데이터 값보다 크다면
                elif val > current.info:
                	# 현재 노드의 오른쪽 노드가 있다면
                    if current.right:
                    	# 삽입할 탐색 위치를 현재 노드의 오른쪽 노드로 변경
                        current = current.right
                    # 현재 노드의 오른쪽 노드가 없다면
                    else:
                    	# val 값을 갖는 노드를 생성하여 현재 노드의 오른쪽 노드에 할당
                        current.right = Node(val)
                        # 데이터 삽입을 끝냈으니 반복문 종료시키고 끝냄.
                        break
                # 삽입하려는 데이터 값이 현재 노드의 데이터 값과 동일하다면
                else:
                	# 삽입할 필요가 없으니 그냥 끝냄.
                    break

🚢 Input & Output

# 이진 탐색 트리 선언
tree = BinarySearchTree()
# 생성할 노드 개수 입력받기
t = int(input())
# n × 1 사이즈의 리스트 형태의 array 생성
arr = list(map(int, input().split()))
# for문을 돌면서 노드 생성
for i in range(t):
    tree.create(arr[i])

##### 여기에 문제에서 원하는 함수를 입력받아 코드 실행하게 됨 ####

🚊 Tree 순회 구현

제약조건

Nodes in the tree

출력 형식

Print the tree's preorder traversal as a single line of space-separated values.

입력 예시

     1
      \
       2
        \
         5
        /  \
       3    6
        \
         4  

출력 예시

# Preorder
	1 2 5 3 4 6 
# Inorder
	1 2 3 4 5 6 
# Postorder
	4 3 6 5 2 1 
# Levelorder
	1 2 5 3 6 4
    

🚊 순회 방식별 살펴보기

🚢 Preorder

🚥 Root Node → left Node → right Node

📑 Code

def PreOrder(root):
	# root 노드가 있다면
	if root:
    	# 현재 노드의 데이터를 출력하고
    	print(root.info, end=" ")
        # 현재 노드의 왼쪽에서 PreOrder를 다시 진행
        # → 왼쪽으로 한 단계 들어가는 것을 의미
        PreOrder(root.left)
        # 현재 노드의 왼쪽에서 Preorder가 끝났다면, 오른쪽에서 PreOrder를 다시 진행
        # → 오른쪽으로 한 단계 들어가는 것을 의미
        PreOrder(root.right)

• root 노드에서 현재 노드의 데이터를 출력하고
• 그 다음에 왼쪽 노드로 내려가서 해당 노드의 데이터를 출력
• 위의 과정을 반복
• 더이상 파고들 왼쪽 노드가 없으면 바로 이전 노드로 돌아가 해당 노드의 오른쪽 노드로 내려감.
• 이 과정을 끝까지 반복

🚢 Inorder

🚥 left Node → Root Node → right Node

📑 Code

def inOrder(root):
	# root 노드가 있다면
	if root:
        # 현재 노드의 왼쪽에서 inOrder를 다시 진행
        inOrder(root.left)
    	# 현재 노드의 데이터를 출력
    	print(root.info, end=" ")
        # 현재 노드의 오른쪽에서 inOrder를 다시 진행
        inOrder(root.right)

• root 노드부터 현재 노드의 왼쪽 노드로 내려가는 과정을 반복
• 현재 노드 기준, 더이상 파고들 왼쪽 노드가 없으면 현재 노드의 데이터를 출력
• 바로 이전 노드로 돌아가 해당 노드의 데이터를 출력
• 그 노드의 오른쪽 노드로 내려가서 해당 노드의 데이터를 출력
• 이 과정을 끝까지 반복

🚢 Postorder

🚥 Root Node → left Node → right Node

📑 Code

def postOrder(root):
	# root 노드가 있다면
	if root:
        # 현재 노드의 왼쪽에서 postOrder를 다시 진행
        postOrder(root.left)
        # 현재 노드의 오른쪽에서 postOrder를 다시 진행
        postOrder(root.right)
    	# 현재 노드의 데이터를 출력
    	print(root.info, end=" ")

• root 노드부터 현재 노드의 왼쪽 노드로 내려가는 과정을 반복
• 더이상 파고들 노드가 없으면 현재 노드의 오른쪽 노드로 내려감
• 현재 노드의 데이터를 출력
• 이 과정을 끝까지 반복

🚢 Levelorder

🚥 Root Node → left Node → right Node

• 각 Level의 노드를 왼쪽부터 출력 후, 그 다음 Level로 넘어가 이 과정을 반복

📑 Code

from collections import deque

def levelOrder(root):
    if not root:
    	return 
    
    # deque 생성
    queue = deque()
    # root 노드를 추가
    queue.append(root)
    # queue에 아무 것도 없을 때까지 반복
    while queue:
    	# queue의 첫 번째 객체를 추출하여 현재 노드에 할당
        current_node = queue.popleft()
        # 현재 노드의 데이터를 출력
        print(current_node.info, end = ' ')
        # 현재 노드의 왼쪽 노드가 있다면?
        if current_node.left: 
        	# queue에 해당 노드를 추가
            queue.append(current_node.left)
        # 현재 노드의 오른쪽 노드가 있다면?
        if current_node.right: 
        	# queue에 해당 노드를 추가
            queue.append(current_node.right)

• FIFO(First In First Out) 방식의 Queue 자료구조를 사용하기 위해 collections 모듈의 deque을 import
• 상위 Level부터 노드들을 순서대로 담을 queue를 deque 자료구조로 선언
• root 노드부터 시작하여 해당 노드의 왼쪽 노드와 오른쪽 노드가 순서대로 queue에 쌓이게 됨.
• 노드 데이터의 출력은 queue에서 왼쪽부터 뽑혀 나와 진행되기 때문에 상위 Level부터 시작해서 현재 노드의 왼쪽부터 오른쪽으로 순서대로 출력되고 그 다음 Level로 넘어가서 반복되는 형태로 진행됨.