[엘리스] 이진트리 만들기

이진트리 만들기

이번 예제에서는 주어진 입력으로부터 이진트리를 만드는 프로그램을 작성합니다.

그 후 만들어진 이진트리를 이용하여 전위순회, 중위순회, 후위순회 한 결과를 출력하세요.

[입력값]

• 〔1〕 n: 노드의 개수
• 〔2~〕 a b c
  정점 a가 왼쪽 자식으로 b, 오른쪽 자식으로 c를 갖는다는 의미입니다. 만약 노드의 자식 노드가 없다면 -1이 주어집니다. 노드의 정보가 주어질 때는, 항상 부모노드의 정보가 먼저 주어진다고 가정해도 좋습니다.

[결과값]

• 〔1〕 전위순회 한 결과
• 〔2〕 중위순회 한 결과
• 〔3〕 후위순회 한 결과

[입력 예시]

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

풀이

class Tree:
    def __init__(self, i, l, r) :
        self.index = i
        self.left = l
        self.right = r

    def addNode(self, i, l, r) :
        '''
        트리 내의 정점 i에 대하여 왼쪽자식을 l, 오른쪽 자식을 r로
        설정해주는 함수를 작성하세요.
        '''
        # 자식이 없는 Node i에 대해서 왼쪽에는 l을 오른쪽에는 r을 달아준다.
        # 하지만, Node i의 위치를 모르므로 먼저 i를 찾는 작업이 진행되어야 한다. 

        # self.index가 i인 경우는 찾았으므로 l과 r을 넣어주면 됨 
        # self.index가 아예 없는 경우는 i가 애초에 존재하지 않으니 i를 만들어주고 l과 r을 넣어주면 됨 
        if self.index == i or self.index == None : # 찾았다.
            self.index = i # 백지인 경우에는 초기값을 줘야한다.

            # 자식이 아예 없는 addNode의 경우 None값을 집어넣어 준다. 
            if l == None:
                self.left = None
            else :
                self.left = Tree(l,None,None) # self.left = l 이라 하면 안 된다. -> tree 객체를 넣어줘야 함

            if r == None:
                self.right = None
            else :
                self.right = Tree(r,None,None)

            return True

        # self.index가 i가 아닌 경우, i를 찾아주는 작업을 진행해야 한다. 
        else: 
            # 왼쪽 or 오른쪽에 가서 찾고 추가해달라 -> 전위순회
            if self.left != None :
                flag = self.left.addNode(i, l, r)
                # 있으면 넣어 줄거임, but 없다면, 값을 반환하여 if에 넣어주면 된다.
                # flag == True: 추가 했어, flag == False: 추가 안됨
                # True, False: 반환하도록 해줘야한다.
            else :
                flag = False

            # 왼쪽에서 찾으면 종료, 그렇지 않으면 오른쪽에서 찾기 
            if flag == True :
                return True
            else :
                if self.right != None :
                    flag = self.right.addNode(i, l, r) # 오른쪽에게 시킨다.
                else :
                    flag = False

                if flag == True :
                    return True # 있다.
                else :
                    return False # 없다.

# 추가한 트리를 바탕으로 전위, 중위, 후위순회를 진행 
# 재귀호출을 이용해서 자동적으로 진행할 수 있음 
def preorder(tree) :
    result = []

    result.append(tree.index)

    if tree.left != None :
        result = result + preorder(tree.left)

    if tree.right != None :
        result = result + preorder(tree.right)

    return result

def inorder(tree) :
    result = []

    if tree.left != None :
        result = result + inorder(tree.left)

    result.append(tree.index)

    if tree.right != None :
        result = result + inorder(tree.right)

    return result

def postorder(tree) :
    result = []

    if tree.left != None :
        result = result + postorder(tree.left)

    if tree.right != None :
        result = result + postorder(tree.right)

    result.append(tree.index)

    return result

def main():
    myTree = Tree(None, None, None)

    n = int(input())

    for i in range(n) :
        myList = [int(v) for v in input().split()]

        if myList[1] == -1 :
            myList[1] = None

        if myList[2] == -1 :
            myList[2] = None

        myTree.addNode(myList[0], myList[1], myList[2])

    print(*preorder(myTree))
    print(*inorder(myTree))
    print(*postorder(myTree))


if __name__ == "__main__":
    main()

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn