[Python] 백준 1991 트리 순회

 

문제 분석

문제 유형 : 트리

• 이진 트리를 입력받아 전위 순회, 중위 순회, 후위 순회한 결과를 출력
  • 전위 트리 : 루트 - 왼 - 오
  • 중우 트리 : 왼 - 루트 - 오
  • 후위 트리 : 왼 - 오- 루트
• 트리 노드의 개수 n 

 

코드 설계

• 노드의 개수가 주어짐
• 각 노드에 대해 왼쪽 자식 / 오른쪽 자식
• 입력되는 순서는 루트 - 왼 - 오
• 루트의 (인덱스) * 2와 같은 값이면 왼쪽 자식 노드
• 루드의 (인덱스+1) * 2
  
  
• 깊이가 d일 때 트리의 최대 노드 수 = 2**d-1
  • n이 주어지면 2**d-1 값을 d=1,2,3,4.. 증가시키는데 만약 n보다 d~값이 더 크거나 같은 순간이 오면 그때의 d~값의 크기만큼 리스트 선언
  • or n은 최대 26 : 아예 26개 선언해버리기..
• n이 주어지면 최대 노드 수를 설정해놓고 해당 인덱스에 값 넣기

 

1. 값을 리스트에 담기
   1. 항상 A가 루트 노트 : tree[0] = A
   2. A부터 시작해서 n번 3개씩 입력을 받음
   3. 루트 - 루트의 (인덱스*2+1) - 루트의 (인덱스*2+2)의 각 인덱스에 값 넣기

n개의 수를 출력해야하니 출력 리스트이 값이 n일 때까지 반복

• 전위 순회 (Preorder Traversal)
  1. 현재 노드를 출력
  2. 왼쪽 자식 노드가 있다면 왼쪽으로 이동하고 (1)부터 반복
  3. 왼쪽 자식이 없다면 오른쪽으로 이동하고 (1)부터 반복
  4. 자식 노두를 모두 방문하면 부모 노드로 되돌아감
  5. 부모 노드에서 방문하지 않은 오른쪽 자식이 있다면 (2)부터 반복
  6. 1. 루트 출력
     2. 루트의 왼쪽 노드 확인하고 있으면 출력 → 방금 출력한 노드가 루트가 됨
     3. 만약 왼쪽 노드가 없다면 오른쪽 노드 출력 → 출력한 오른쪽 노드가 루트가 되어 다시 왼쪽 노드 찾기
     4. 자식 노드가 다 출력되었다면 자신의 부모 노드로 올라감
     5. 부모 노드도 다 출력되었는지 확인
     6. 다 출력이 안된 상태라면 안 된 노드를 루트로 삼아서 왼쪽 확인하는 거 반복

• 중위순회 (Inorder Traversal)
  1. 현재 노드의 왼쪽 자식이 있으면 왼쪽으로 이동
  2. 더 이상 왼쪽 자식이 없으면 현재 노드를 출력
  3. 오른쪽 자식이 있으면 오른쪽 자식으로 이동하고 다시 (1)부터 반복
  4. 오른쪽 자식이 없으면 부모 노드로 되돌아감
  5. 부모 노드에서 아직 방문하지 않은 오른쪽 자식이 있으면 (3)부터 반복
• 후위 순회 (Postorder Traversal)
  1.  현재 노드의 왼쪽 자식이 있으면 왼쪽으로 이동
  2. 더 이상 왼쪽 자식이 없으면 오른쪽 자식 확인
  3. 오른쪽 자식이 있으면 오른쪽으로 이동하고 다시 (1)부터 반복
  4. 왼쪽과 오른쪽 자식을 모두 방문한 후에 현재 노드를 출력
  5. 부모 노드로 되돌아가고, 부모의 오른쪽 자식이 아직 방문되지 않았다면 (3)부터 반복

 

정답 코드

하..

import sys
input = sys.stdin.readline

n = int(input())
tree = [''] * 100
tree[0] = 'A' # 루트는 무조건 A

# 입력값들을 리스트에 넣기
for _ in range(n) :
    nums = list(input().split())
    root_idx = tree.index(nums[0])
    tree[root_idx*2 + 1] = nums[1]
    tree[root_idx*2 + 2] = nums[2]

# 전위 순위
root = 0
pre_tree = tree
pre_check = [[False] * len(pre_tree)] # 한번 출력한거는 또 출력 x
pre_print = []
# or arrPrint에 있는지를 체크?
while (len(pre_print) < n) :
    pre_print.append([pre_tree[root]]) # 1. 루트 출력
    if pre_tree[root*2+1] != '' or pre_tree[root*2+1] != '.' : # 값이 있으면
        pre_print.append([pre_tree[root]])
        root = 

# 중위 순위
in_tree = tree

# 후위 순위
post_tree = tree

 

 

다른 정답 코드 1 : https://velog.io/@ohk9134/%EB%B0%B1%EC%A4%80-1991%EB%B2%88-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-python-%ED%8A%B8%EB%A6%AC-%EA%B5%AC%ED%98%84

 

① Python으로 트리 구현하는 방법 : dictionary(사전) 사용

전위 순회, 중위 순회, 후위 순회를 하는 함수를 각각 구현한다. 전위 순회는 root -> left -> right 순서로, 중위 순회는 left -> root -> right 순서로, 후위 순회는 left -> right -> root 순서로 탐색해야 한다. 이를 위해 각 함수를 재귀함수로 구현해주었고, 각 함수의 탐색 순서에 따라서 left 혹은 right를 root으로 넣어주는 재귀 구조를 만들었다.

import sys
 
N = int(sys.stdin.readline().strip())
tree = {}
 
for n in range(N):
    root, left, right = sys.stdin.readline().strip().split()
    tree[root] = [left, right]
 
 # root -> left -> right 순서
def preorder(root):
    if root != '.':
        print(root, end='')  # root
        preorder(tree[root][0])  # left
        preorder(tree[root][1])  # right
 
 # left -> root -> right 순서
def inorder(root):
    if root != '.':
        inorder(tree[root][0])  # left
        print(root, end='')  # root
        inorder(tree[root][1])  # right
 
 # left -> right -> root 순서
def postorder(root):
    if root != '.':
        postorder(tree[root][0])  # left
        postorder(tree[root][1])  # right
        print(root, end='')  # root
 
 
preorder('A')
print()
inorder('A')
print()
postorder('A')

 

root를 key로 / left, right 자식들을 value로 할당한다.
tree[root] = left, right

tree = {}
tree["A"] = "B", "C"

이렇게 tree의 인덱스는 KEY로, 저장되는 값은 VALUE로 사전에 저장할 수 있다.
{"A" : ("B","C")}
👉 의미 : A가 부모인 노드가 B, C / A의 자식이 B, C

※ A를 key로 가지는 value인 B를 인덱싱하는 방법 : tree["A"][0]

 

② 전위 / 중위 / 후위 순회마다 재귀함수 코드의 순서 바꾸기

# 한번 재귀할 때마다 탐색을 한번 더 하는 의미로 받아들이자
# 함수 안의 ~~order(tree[root][0]) 재귀함수는 왼쪽으로 끝까지 탐색한다는 의미
# 함수 안의 ~~order(tree[root][1]) 재귀함수는 오른쪽으로 끝까지 탐색한다는 의미
# root -> 출력하면 됨


# 1. 전위 순회 : 루트 -> 왼쪽 자식 -> 오른쪽 자식이므로 재귀함수 순서도 root출력문 -> 왼쪽 재귀함수 -> 오른쪽 재귀함수

def preorder(root): # 루트 -> 왼쪽 자식 -> 오른쪽 자식 순으로 탐색
    if root != '.':
        print(root, end='')  # root
        preorder(tree[root][0])  # left -> left가 새로운 root가 된다.
        preorder(tree[root][1])  # right -> right가 새로운 root가 된다.
        

# 2. 중위 순회 : 왼쪽 자식 -> 루트 -> 오른쪽 자식이므로 재귀함수 순서도 왼쪽 재귀함수 -> root 출력문 -> 오른쪽 재귀함수
 
def inorder(root): # 왼쪽 자식 -> 루트 -> 오른쪽 자식 순으로 탐색
    if root != '.': 
    # TEST CASE를 예로 들면 B에서 tree[root][0] = "D"이고 D의 tree(root[0]) = "."이 돼서 root인 D를 출력하고 right로 넘어간다.
        inorder(tree[root][0])  # left
        print(root, end='')  # root
        inorder(tree[root][1])  # right


# 3. 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 루트이므로 재귀함수 순서도 왼쪽 재귀함수 -> 오른쪽 재귀함수 -> root 출력문

def postorder(root): # 왼쪽 자식 -> 오른쪽 자식 -> 루트 순으로 탐색
    if root != '.':
        postorder(tree[root][0])  # left
        postorder(tree[root][1])  # right
        print(root, end='')  # root

 

 

다른 정답 코드 2 : https://define-me.tistory.com/79

import sys
input = sys.stdin.readline
n = int(input())

inputs = []
for _ in range(n):
    inputs.append(input().split())

class Node():
    def __init__(self, item, left, right):
        self.item = item
        self.left = left
        self.right = right

def preorder(node):
    print(node.item, end = '')
    if node.left != '.':
        preorder(tree[node.left])
    if node.right != '.':
        preorder(tree[node.right])
        
def inorder(node):
    if node.left != '.':
        inorder(tree[node.left])
    print(node.item, end = '')
    if node.right != '.':
        inorder(tree[node.right])
        
def postorder(node):
    if node.left != '.':
        postorder(tree[node.left])
    if node.right != '.':
        postorder(tree[node.right])
    print(node.item, end = '')

tree = {}
for item, left, right in inputs:
    tree[item] = Node(item, left, right)
preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])