파이썬으로 알고리즘, 자료구조 공부하기 - 트리(tree), 이진트리(binary tree)

지난 포스팅까지 파이썬으로 연결 리스트(linked list)와 스택(stack), 큐(queue)를 공부했다.

이번에는 트리 구조이다

트리는 정말 많이 쓰인다. 일단 리눅스 구조만 봐도 트리구조이다.

간단하게는 족보라고 생각하면 좋다

맨 위에 최초 조상님이 계실거고 그 밑에 자녀들 등등 해서 족보가 그려진다.

 

 

이런 구조가 트리구조라고 할 수 있다. 트리도 뭐 이진 트리냐, 완전 이진트리냐 등등이 있다.

보통 이진트리가 많이 사용된다.

트리에는 root와 부모 노드(parent node), 자식 노드(child node)가 있다. 위의 구조에서 root는 A이고 A의 자식은 B, C이다. 그리고 B,C의 부모는 A이다. 이런 식으로 부모, 자식 노드를 구분할 수 있다.

형제 노드(sibling node)도 있는데 D, E는 B가 부모 노드지만 서로는 형제 노드가 된다. 즉 같은 부모 밑에서 파생된 바로 아래 자식 노드들이다. 

그리고 레벨(level)과 높이(height)가 있다. A는 레벨로 따지면 레벨 0이다. 그리고 B,C 라인이 1이고 G,H,I 라인이 3이된다. 높이는 3이다. 즉, 높이 값은 레벨의 가장 높은 값으로 생각하면 된다!

차수(degree) 개념도 있다. 트리에서 차수(degree)는 서브 트리의 개수이다. 위에선 A 기준 subtree가 2개이므로(B라인, C라인) 차수는 2이다.

이렇게 차수가 2이하인 트리를 이진 트리(binary tree)라고 한다

그리고 트리에는 순회(traverse) 알고리즘이 있다.

보통 전위 순회(pre-order traverse), 중위 순회(in-order traverse), 후위 순회(post-order traverse) 이렇게 3개로 나뉘어져 있다.

전위 : Root -> 왼 -> 오

중위 : 왼 -> Root -> 오

후위 : 왼 -> 오 -> Root

라고 생각하면 된다

무슨 말인가 하면

 

 

이게 전위 순회이다. Root부터 보고 그 다음 왼쪽 노드로 가서 그 부분에서 root를 보고 그 다음에 또 왼쪽이 있으면 그 부분에서 root를 보고 없으면 오른쪽 보고.. 이런 방법으로 진행된다. 그래서 위 구조에서 전위 순회를 하게 되면 위 처럼  A->B->D..가 나오게 된다

 

 

마찬가지로 중위 순회를 따라가게 되면 위 처럼 나온다. 왼쪽을 먼저 보고 그 다음 root, 그리고 오른쪽을 본다

 

 

 

후위 순회를 보게 되면 위 처럼 나오게 될 것이다. 왼 -> 오 -> root 방식이다

 

그럼 파이썬 코드로 트리를 어떻게 만들 수 있을까?

쉽게 이진 트리(binary tree)를 만들어보자

 

 

이런 구조를 만든다

 

 

간단하다. class를 하나 만들고 node 클래스 밑에 생성자로 self.data, self.left, self.right를 둔다

그리고 A 노드를 만들고 그 왼쪽(root.left)에 B를, 오른쪽에 C를 이렇게 만들어주면 된다

자 그럼 여기에서 아까 본 전위 순회, 중위 순회, 후위 순회를 만들어보자

먼저 전위 순회이다

 

 

전위 순회는 위와 같이 만든다.

먼저 node가 들어오면 얘는 root부터 보고 왼쪽 그리고 오른쪽을 본다.

그래서 root를 먼저 찍어주고 그 다음으로 왼쪽 기준으로 가야하니까 함수를 node.left 기준으로 먼저 호출 시킨다. 그리고 왼쪽이 없으면 오른쪽을 호출시킨다

 

 

그러면 위 처럼 출력이 될 것이다!

다음은 중위 순회이다

중위 순회는 왼쪽으로 먼저 간 다음 데이터를 출력시키고 오른쪽으로 가면 된다

즉 왼 -> root -> 오 방법이다

 

 

 

아까 함수와 똑같지만 print를 어디에 두느냐에 따라 다르다.

아까 함수랑 완전히 똑같다. inorder_traverse를 만들어서 해준다.

 

 

후위 순회도 아까 함수랑 완전히 똑같다. 대신 print만 어디로 해줄지가 달라진다.

 

전체를 출력해보면 이렇게 나온다.

그래서 전위 방법이냐, 중위 방법이냐, 후위 방법이냐에 따라 데이터를 어떻게 접근하는지 다르다.

그리고 위 방법론은 정보처리기사 등 다양하게 출제가 된다

 

여기까지 파이썬을 활용해서 간단하게 트리 알고리즘을 구성해봤다!