[ 5639 ] [ Tree ] 이진 검색 트리

문제 설명

---

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

---

풀이 과정

1. 전위 순회는 루트를 먼저 순회하므로, 전위 순회한 순서대로 노드를 넣어서 이진 검색 트리를 만들면 문제와 똑같은 트리가 만들어 진다.
   • 현재 노드보다 작으면 왼쪽 자식 노드
   • 현재 노드보다 크면 오른쪽 자식 노드
   • 자식 노드가 None인 경우 거기다가 넣어준다.
2. 후위 순회의 경우 recursion으로 구현한다. (left -> right -> 루트)
3. 입력 종료 글자가 없으므로 try..except로 입력 종료

---

소스 코드

import sys

sys.setrecursionlimit(10**5)

class tree_node():
    def __init__(self, element):
        self.left = None
        self.right = None
        self.element = element


def push_tree(tree, element):
    if tree.element == None: # 맨 위 루트노드는 초깃값 None
        tree.element = element
    else:
        temp = tree_node(element)
        while True:
            # 현재 트리의 요소보다 입력값이 크면 오른쪽
            if tree.element < element:
                if tree.right == None:
                    tree.right = temp
                    break
                else:
                    tree = tree.right
            # 작으면 왼쪽
            else:
                if tree.left == None:
                    tree.left = temp
                    break
                else:
                    tree = tree.left

def post_order(tree):
    if tree == None:
        return
    post_order(tree.left)
    post_order(tree.right)
    print(tree.element)

Tree = tree_node(None)
while True:
    try:
        p = int(input())
        push_tree(Tree, p)
    except:
        break

post_order(Tree)