[03-15] Tree 구조

1. 개요 & 알고리즘

지금까지는 진행한 것들은 모두 선형적 자료 구조(Linear structure)"였지만, Tree는 비선형적 자료 구조(Non-linear structure)이며, 2차원적인 구조입니다. 뿌리(root)와 가지(link)로 구성되며, 잎(leaf)들이 달려 있는, 마치 나무의 모양을 거꾸로 뒤집어 놓은 모양입니다.^[각주:1] 

트리 구조는 뿌리 노드로부터 다른 노드에 이르는 경로(path)가 오직 하나 밖에 존재하지 않습니다. 이것은 트리 구조가 그래프 구조와 다른점입니다.

제일 마지막 레벨을 제외하고는 각 레벨의 노드가 꽉 차 있는 이진 트리를 완전한 이진 트리(complete binary tree)라고 하며, 모든 레벨이 꽉 차 있는 이진 나무를 꽉 차 있는 이진 나무(full binary tree)라고 합니다.

네 가지의 나무타기(Tree traverse) 방법이 있는데 이들은 각각 나무의 모든 노드들을 한 번씩 중복없이 순회하는 방법^[각주:2]을 제공합니다.

1. 뿌리를 먼저 타는 방법(전회순회, Preorder traverse)

2. 뿌리를 중간에 타는 방법(중위순회, Inorder traverse)

3. 뿌리를 나중에 타는 방법(후위순회, Postorder traverse)

4. 층별로 타는 방법(층별순회, Level order traverse)

(C로 배우는 알고리즘"^[각주:3])

기본적으로는 뿌리에서 시작해서 알고리즘에 맞는 방식에 따라서 원하는 위치를 찾아가고, 원하는 Node를 찾아서 처리하는 방식입니다.

트리 구조에 대해서는 계속 포스팅을 하게될 것입니다. 일단 수식 나무(Parse tree)^[각주:4]에 대해서 구현해봅니다. 수식 나무에서 외부 노드들은 모두 피연산자들이며, 내부 노드들은 모두 연산자들입니다.

후위 표기법을 입력으로 해서 수식 나무를 구성하는 알고리즘은 다음과 같습니다.

1. 피연산자를 만나면 node를 생성하여 stack에 push한다.

2. 연산자를 만나면 node를 생성하여

2.1 Stack에서 pop한 node를 오른쪽 자식으로 할당하고

2.2 Stack에서 또 pop한 node를 왼쪽 자식으로 할당한다.

2.3 그리고 연산자 node를 stack에 push한다.

3. Stack에서 마지막으로 남은 node가 뿌리 노드가 된다.

수식

((((A+B)*(C-D))/E) +(F*G))

을 후위 표기법으로 변환하면 아래와 같습니다.

A B + C D - * E / F G * +

이것을 위의 알고리즘에 맞춰 Tree로 구성하면 아래와 같습니다.^[각주:5]

2. 동작 코드

연산이 사용 가능한지를 판단하는 함수입니다.

def is_legal(self, equation):
    num_of_operator = 0
    size = len(equation)
    step = 0
    while size != step:
        while equation[step] == ' ':
            step += 1
        if self.is_operator(equation[step]):
            num_of_operator -= 1
        else:
            num_of_operator += 1
        if num_of_operator < 1:
            break
        step += 1

    if num_of_operator == 1:
        return True
    else:
        return False

List의 element를 옮겨가면서 확인합니다.

후위 표기법 수식에서 수식 나무를 구성하는 함수입니다.

def make_parse_tree(self, equation):
    while len(equation) != 0:
        while equation[0] == ' ':
            del equation[0]
        node = Node()
        node.key = equation[0]
        node.left = self.tail
        node.right = self.tail
        if self.is_operator(equation[0]):
            node.right = self.stack.pop()
            node.left = self.stack.pop()
        self.stack.append(node)
        del equation[0]
    self.head.right = self.stack.pop()

위의 is_legal()과 달리 List의 element를 옮겨가면서 진행하지 않고, delete를 해가면서 연산을 했습니다. 위 연산이 끝나면 실제 데이터는 모두 사라지게 됩니다. 따라서 is_legal()로 구현하고, 이후에 make_parse_tree()를 호출하면, make_parse_tree()는 처리할 equation이 없어서 에러가 발생합니다.

3. 실행 코드

중위 표기법으로 수식을 입력 받아서 후위 표기법으로 변환한 후, 수식 나무를 구성하고, 네 가지의 나무타기 방법으로 수식 나무의 내용을 출력하는 프로그램입니다("C로 배우는 알고리즘" 리스트 3-14 : TREE1.C에 대응) 

중위 표기법을 후위 표기법으로 변경하는 프로그램은 앞선 포스팅^[각주:6]을 그대로 이용하였습니다.

후위 표기법으로 변환한 후에는 수식 나무로 구성한 후, 앞서 Tree를 순회하는 방법 4가지에 따라서 순회하도록 했습니다.

# main() function
if __name__ == "__main__":
    # Change infix notation to postfix notation
    source = "((((A+B)*(C-D))/E)+(F*G))"#input("Please input -> ")
    postfix = Postfix()
    contents = postfix.do_postfix(source)
    print(contents)
    #
    tree = Tree()
    if tree.is_legal(contents) is not True:
        print ("Expression is not legal")
    else:
        tree.make_parse_tree(contents)
        tree.preorder_traverse(tree.head.right)
        print()
        tree.inorder_traverse(tree.head.right)
        print()
        tree.postorder_traverse(tree.head.right)
        print()
        tree.levelorder_traverse(tree.head.right)
        print()

4. Tips

1. Python에서는 Node class와 같은 것도 append 함수로 List에 추가할 수 있었습니다.

2. Class 내부적으로만 사용하는 method에 대해서는 @staticmethod를 함수 위에 적어서 Class 외부에서는 사용할 수 없음을 명확히 했습니다.^[각주:7]

@staticmethod
def visit(n):
    print(n.key, end=" ")

3. Queue는 따로 구현하지 않고, Python이 제공하는 Queue를 그대로 사용했습니다.^[각주:8]

5. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_15.py

1. http://onestep.tistory.com/42 [본문으로]
2. http://3dmpengines.tistory.com/423 [본문으로]
3. http://www.yes24.com/24/goods/18003 [본문으로]
4. http://ddmix.blogspot.kr/2014/12/cppalgo-7-tree.html [본문으로]
5. https://yohasebe.com/rsyntaxtree/ [본문으로]
6. http://steadyandslow.tistory.com/110 [본문으로]
7. http://schoolofweb.net/blog/posts/%ED%8C%8C%EC%9D%B4%EC%8D%AC-oop-part-4-%ED%81%B4%EB%9E%98%EC%8A%A4-%EB%A9%94%EC%86%8C%EB%93%9C%EC%99%80-%EC%8A%A4%ED%83%9C%ED%8B%B1-%EB%A9%94%EC%86%8C%EB%93%9C-class-method-and-static-method/ [본문으로]
8. http://sarangyik.tistory.com/entry/Pythonmodule-queue [본문으로]