Assignment 4 - Tree orders

Assignment 4 - Tree orders

이번 마지막 과제는 5문제 중 3개만 통과하면 된다.

1번 과제는 Binary tree를 in-order, pre-order, post-order에 따라 정렬하는 것이다.

Input :
n (vertices)
keyi, lefti, righti (key value, left child, right child)

Output :
in-order vertices
pre-order vertices
post-order vertices

첫번째 샘플을 보면 5개의 노드가 있음을 알리고 이후 0번째 노드의 key 값은 4, 왼쪽 자식노드는 1번째 노드, 오른쪽 자식노드는 2번째 노드임을 알 수 있다. 이후 같은 규칙으로 진행되며 자식노드가 없을 시 -1로 표기한다.

# python3
import sys, threading
sys.setrecursionlimit(10**6) # max depth of recursionthreading.stack_size(2**27)  # new thread will get stack of such size
class TreeOrders:
  def read(self):
    self.n = int(sys.stdin.readline())
    self.key = [0 for i in range(self.n)]
    self.left = [0 for i in range(self.n)]
    self.right = [0 for i in range(self.n)]
    for i in range(self.n):
      [a, b, c] = map(int, sys.stdin.readline().split())
      self.key[i] = a
      self.left[i] = b
      self.right[i] = c

  def inOrder(self):
    self.result = []
    # Finish the implementation    # You may need to add a new recursive method to do that                    return self.result

  def preOrder(self):
    self.result = []
    # Finish the implementation    # You may need to add a new recursive method to do that                    return self.result

  def postOrder(self):
    self.result = []
    # Finish the implementation    # You may need to add a new recursive method to do that                    return self.result

def main():
   tree = TreeOrders()
   tree.read()
   print(" ".join(str(x) for x in tree.inOrder()))
   print(" ".join(str(x) for x in tree.preOrder()))
   print(" ".join(str(x) for x in tree.postOrder()))

threading.Thread(target=main).start()

기본틀이며 inOrder, preOrder, PostOrder의 내용을 채우면 되며 친절히 recursive method를 사용해야 한다고 힌트를 주고있다.

# python3
import sys, threading
sys.setrecursionlimit(10**6) # max depth of recursionthreading.stack_size(2**27)  # new thread will get stack of such size

class TreeOrders:
    def read(self):
        self.n = int(sys.stdin.readline())
        self.key = [0 for i in range(self.n)]
        self.left = [0 for i in range(self.n)]
        self.right = [0 for i in range(self.n)]
        for i in range(self.n):
            [a, b, c] = map(int, sys.stdin.readline().split())
            self.key[i] = a
            self.left[i] = b
            self.right[i] = c

    def inOrder(self):
        self.result = []
        # Finish the implementation        # You may need to add a new recursive method to do that
        def _inorder_trav(root):
            if root == -1:
                pass            else:
                _inorder_trav(self.le_ch(root))
                self.result.append(root)
                _inorder_trav(self.ri_ch(root))

        _inorder_trav(self.key[0])
        return self.result

    def preOrder(self):
        self.result = []
        # Finish the implementation        # You may need to add a new recursive method to do that
        def _preorder_trav(root):
            if root == -1:
                pass            else:
                self.result.append(root)
                _preorder_trav(self.le_ch(root))
                _preorder_trav(self.ri_ch(root))

        _preorder_trav(self.key[0])
        return self.result

    def postOrder(self):
        self.result = []
        # Finish the implementation        # You may need to add a new recursive method to do that
        def _postorder_trav(root):
            if root == -1:
                pass            else:
                _postorder_trav(self.le_ch(root))
                _postorder_trav(self.ri_ch(root))
                self.result.append(root)

        _postorder_trav(self.key[0])
        return self.result

    def le_ch(self, root):
        if self.left[self.key.index(root)] == -1:
            left = -1        else:
            left = self.key[self.left[self.key.index(root)]]
        return left

    def ri_ch(self, root):
        if self.right[self.key.index(root)] == -1:
            right = -1        else:
            right = self.key[self.right[self.key.index(root)]]
        return right


def main():
    tree = TreeOrders()
    tree.read()
    print(" ".join(str(x) for x in tree.inOrder()))
    print(" ".join(str(x) for x in tree.preOrder()))
    print(" ".join(str(x) for x in tree.postOrder()))


threading.Thread(target=main).start()

각 order 정렬의 특성상 어디로 접근하여 값을 추가할 것인지만 순서를 잘 잡으면 된다. left child와 right child의 값을 반환해주는 메쏘드도 추가하였다.