Binary Tree
앞서 자료구조 중 Heap에 대해서 알아 보았다.
Heap은 Binary Tree(이진트리)의 한 종류이며, 힙성질과 모양성질 조건을 충족한 자료구조이다.
그렇다면 이진트리는 무었인가?
이진트리란, 리프노드의 수가 하나도 없거나, 1개거나 2개인 트리 형태의 자료구조를 의미한다.
heap의 경우 트리를 표현하는 방법1을 통해서 배열과 리스트를 이용해서 자료구조를 구현해서 상수시간안에 부모노드, 왼쪽, 자식노드의 값을 구했다.
이진트리는 트리를 표현하는 방법3을 통해서 직접 node 클래스를 정의해서 구현할 수 있다.
class Node:
def __init__(self, key):
self.key = key
self.parent = self.left = self.right = None
def __str__(self):
return str(self.key)이진트리에는 insert(), delete(), serch()와 같은 메서드가 있다.
순회(traversal)
순회란 트리의 모든 노드를 돌면서, 노드의 key값을 모두 출력하는 것이다.
트리의 순회 방법으로는 preorder, inorder, postorder 3가지 방법이 있다.
단어 뜻 그대로 루트노드가 어디에 있는지에 따라 순회방법이 달라진다.
pre는 앞, in은 중간, post는 맨 끝에 루트노드를 두고 순회한다.
pre => 루트노드, 왼쪽노드, 오른쪽노드
in => 왼쪽노드, 루트노드, 오른쪽노드
post => 왼쪽노드, 오른쪽노드, 루트노드
순회하는 메서드는 node 클래스에 정의해도 되고, 이진트리클래스 안에서 정의해도 된다.
class Node:
def __init__(self, key):
self.key = key
self.parent = self.left = self.right = None
def __str__(self):
return str(self.key)
def inorder(self):
if self != None:
if self.left:
self.left.inorder()
print(self.key)
if self.right:
self.right.inorder()
위에서는 inorder만 정의했지만, preorder와 postorder은 print()문이 어디에 들어가는지에 따라 달라질 뿐이므로 간단히 구현이 가능하다.
이진트리의 모양을 모르는 상태에서 preorder와 inorder가 주어진다면 이진트리 형태로 만들 수 있다. 이를 reconstruct라고 한다.
참조
