[python][트리] 백준 알고리즘 1991번

테스트를 위해 인풋을 파일로 만들었음.
할일

1. 파일을 읽어온다.
2. 파일을 정재하여 리스트에 넣는다.
3. 간단한 트리구조로 변환할 함수를 만든다
4. 트리의 루트를 글로벌로 하나 생성한다.
5. 트리구조의 리스트로 변환한다
6. 전위, 후위, 중위 탐색을 함수를 만든다.
7. 출력한다.

1. 파일을 읽어온다. 2. 파일을 정재하여 리스트에 넣는다.

def readFile(filename):
  with open(filename) as file:
    return [ x.strip('\n').replace(' ','') for x in file.readlines()]
list_ = readFile('1991.txt')

3. 간단한 트리구조로 변환할 함수를 만든다. 4. 트리의 루트를 글로벌로 하나 생성한다.

def my_tree(r):
    return [r, [], []]
root = None

5. 트리구조의 리스트로 변환한다.

def add(data, left, right):
    global root
    if root is None:
        if data != '.':
            root = my_tree(data)
        if left != '.':
            root[1] = my_tree(left)
        if right != '.':
            root[2] = my_tree(right)
        return root
    else:
        return search(root, data, left, right)

def search(root, data, left, right):
    if root is None or root == []:
        return root
    elif root[0] == data:
        if left != '.':
            root[1] = my_tree(left)
        if right != '.':
            root[2] = my_tree(right)
        return root
    else:
        search(root[1], data, left, right)
        search(root[2], data, left, right)


for l_ in list_[1:]:
    add(l_[0],l_[1],l_[2])

6. 전위 후위 중위 탐색 함수를 만든다.

def preorder(root):
    if root:
        print(root[0], end='')
        if root[1]:
            preorder(root[1])
        if root[2]:
            preorder(root[2])

def inorder(root):
    if root:
        if root[1]:
            inorder(root[1])
        print(root[0], end='')
        if root[2]:
            inorder(root[2])

def postorder(root):
    if root:
        if root[1]:
            postorder(root[1])
        if root[2]:
            postorder(root[2])
        print(root[0], end='')

7. 출력한다.

preorder(root)
print()
inorder(root)
print()
postorder(root)
print()