5639. 이진 검색 트리 (Python)

 

5639번: 이진 검색 트리

 

풀이

 트리 클래스를 사용하여 실제로 트리를 구성하여 출력하는 방법과 입력으로 주어진 전위 순회 결과에서 재귀를 사용하여 후위 순회 결과를 얻는 방법으로 문제를 해결할 수 있다.

 

 전자는 Tree 클래스를 만들고 루트 노드의 값으로 트리 객체를 하나 생성한다. 그 후 Tree 클래스의 insert 메서드를 사용하여 트리에 값을 넣어준다. insert 메서드는 부모 노드의 값과 새로 삽입되는 값을 비교하여 작을 경우 왼쪽 트리에 값을 삽입하고 클 경우 오른쪽 트리에 값을 삽입한다. 이 때, 부모 노드의 자식 노드가 비어있으면 그대로 자식 노드에 트리 객체를 만들어주면 되고 비어있지 않다면 다시 자식 노드를 부모 노드로 하는 insert 메서드를 호출하도록 한다.

 후위 순회 출력은 자식 노드가 비어있지 않다면 왼쪽과 오른쪽을 순서대로 출력 메서드를 호출한 후 자신의 값을 출력하도록 만들어준다.

 

 후자는 따로 클래스를 만들지 않고 바로 출력할 수 있는 방법이다. postOrder(nums) 메서드를 만드는데 이 때 파라미터 nums는 입력으로 주어진 전위 순회 결과이다. nums 배열의 인덱스 0의 값은 현재 전위 순회 결과에서 부모 노드에 해당한다. 이제 인덱스 1부터 순차적으로 탐색하여 인덱스 0의 값보다 커지는 값의 인덱스를 구한다. 

 

 예를 들어 위의 값에서 부모 노드의 값은 50이다. 이제 30부터 순차적으로 탐색하여 50보다 값이 커지는 순간을 찾는다. 이는 98에 해당한다. 이를 기준으로 30부터 45까지는 50 노드의 왼쪽 서브 트리에 해당하고 98부터 60까지는 50 노드의 오른쪽 서브 트리에 해당한다. 따라서 먼저 왼쪽 서브 트리에 대하여 재귀적으로 호출하고 다음으로 오른쪽 서브 트리에 대하여 재귀적으로 호출한다. 그리고 마지막에 부모 노드의 값인 50을 출력하도록 하면 후위 순회 결과를 얻을 수 있다.

 

코드

[트리 클래스를 이용한 풀이]

import sys
sys.setrecursionlimit(10 ** 5)

# Tree 클래스


class Tree:
    # 생성자
    def __init__(self, value):
        self.value = value  # 입력으로 받은 값 설정
        self.left = None  # 왼쪽 자식 노드는 None으로 설정
        self.right = None  # 오른쪽 자식 노드는 None으로 설정

    # 값을 삽입하는 insert 메서드
    def insert(self, value):
        if value < self.value:  # 현재 노드의 값 보다 작은 값일 경우 왼쪽에 삽입
            if self.left == None:  # 왼쪽 자식 노드가 비어 있으면 왼쪽 자식 노드로 객체 생성
                self.left = Tree(value)
            else:  # 이미 있다면 왼쪽 자식 노드에 대하여 다시 한 번 insert 메서드 호출
                self.left.insert(value)
        else:  # 현재 노드의 값 보다 큰 값일 경우 오른쪽에 삽입
            if self.right == None:  # 오른쪽 자식 노드가 비어 있으면 왼쪽 자식 노드로 객체 생성
                self.right = Tree(value)
            else:  # 이미 있다면 오른쪽 자식 노드에 대하여 다시 한 번 insert 메서드 호출
                self.right.insert(value)

    # 후위 순회 메서드
    def postOrder(self):
        if self.left != None:  # 왼쪽 자식 노드가 존재하지 않을 때까지 반복해서 메서드 호출
            self.left.postOrder()

        if self.right != None:  # 오른쪽 자식 노드가 존재하지 않을 때까지 반복해서 메서드 호출
            self.right.postOrder()

        print(self.value)  # 자기 자신의 값 호출


if __name__ == '__main__':
    preOrder = []

    while True:
        try:
            num = int(input())
            preOrder.append(num)
        except:
            break

    binaryTree = Tree(preOrder[0])  # 루트 노드를 기준으로 객체 생성

    # 순차적으로 값 삽입
    for i in range(1, len(preOrder)):
        num = preOrder[i]
        binaryTree.insert(num)

    binaryTree.postOrder()

 

 

[클리스 없이 재귀를 사용한 풀이]

import sys
sys.setrecursionlimit(10 ** 5)


# 후위 순회 함수 
def postOrder(nums):
    if len(nums) == 0: # 배열이 비어 있다면 그대로 종료
        return

    if len(nums) == 1: # 배열에 값이 하나 있다면 값 출력한 후 종료 
        print(nums[0])
        return

    idx = len(nums) # 부모 노드를 기준으로 값이 커지는(오른쪽 자식) 순간의 인덱스 
    for i in range(1, len(nums)):
        if nums[i] > nums[0]:
            idx = i
            break

    # 왼쪽 자식 노드에 대하여 재귀 호출 
    if idx > 1:
        postOrder(nums[1:idx])

    # 오른쪽 자식 녿느에 대하여 재귀 호출 
    if idx < len(nums):
        postOrder(nums[idx:])

    # 부모 노드의 값 출력 
    print(nums[0])


if __name__ == '__main__':
    preOrder = []
    while True:
        try:
            num = int(input())
            preOrder.append(num)
        except:
            break

    postOrder(preOrder)