Binary Tree

• definition  출처

이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다. 보통 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽(left)과 오른쪽(right)으로 불린다. 이진 트리는 이진 탐색 트리와 이진 힙의 구현에 흔히 쓰인다.

시간 복잡도

Average                 Worst

Space O(n)             O(n)

Search O(logn)     O(n)

Insert O(logn)     O(n)

Delete O(logn)       O(n)

용도

모든 트리가 이진트리는 아니지만 상당량의 트리들이 이진트리라고 할 수 있습니다. 일단 일반적인 트리들은 LCRS형으로 트리의 역활을 하게되고 또한 힙 트리 ,AVL트리와 레드블랙트리, 스레드 이진 트리 등으로 트리의 역활을 하게 됩니다. 힙 트리를 이용하여 힙 정렬을 사용할 수도 있고 허프만 코드 역시 힙트리를 이용합니다. 트리는 데이터를 저장할 수 있으며 시간복잡도 상으로 우수하기 때문에 여러가지 부수적인 자료구조나 알고리즘을 만드는데도 사용되게 됩니다.

[출처] 09-자료구조: 트리(Tree) -> 이진트리(Binary Tree) -> 이진탐색트리(Binary Search Tree)|작성자 저스트쿠카로

이진 트리 탐색

 

1. in-order : 왼쪽 자식노드, 내 노드, 오른쪽 자식노드 순서로 방문한다.
2. pre-order : 내 노드, 왼쪽 자식노드, 오른쪽 자식노드 순서로 방문한다.
3. post-order : 왼쪽 자식노드, 오른쪽 자식노드, 내 노드 순서로 방문한다.

# class Tree:

[code language="python"]
<span class="keyword">def</span> <span class="function">__init__</span>(self, data, left_child=None, right_child=None):
self.data = data
self.left_child  = left_child
self.right_child = right_child

left_child = Tree(3)
right_child = Tree(4)
parent = Tree(1, left_child, right_child)

def init_tree():

[/code]

create leaf node

[code language="python"]

leaf = []
for i in range(6):
leaf.append( Tree(i+1) )

[/code]

create sub tree

[code language="python"]

left_subtree = Tree(9, Tree(7, leaf[0], leaf[1]), Tree(8, leaf[2], leaf[3]) )
right_subtree = Tree(10, leaf[4], leaf[5])

root = Tree(11, left_subtree, right_subtree)

[/code]

트리 순회

[code language="python"]

def preorder_traverse(tree):
if tree == None: return
print tree.data,
preorder_traverse(tree.left_child)
preorder_traverse(tree.right_child)

def inorder_traverse(tree):
if tree == None: return
inorder_traverse(tree.left_child)
print tree.data,
inorder_traverse(tree.right_child)

def postorder_traverse(tree):
if tree == None: return
postorder_traverse(tree.left_child)
postorder_traverse(tree.right_child)
print tree.data,

[/code]