- 전체
- Python 일반
- Python 수학
- Python 그래픽
- Python 자료구조
- Python 인공지능
- Python 인터넷
- Python SAGE
- wxPython
- TkInter
- iPython
- wxPython
- pyQT
- Jython
- django
- flask
- blender python scripting
- python for minecraft
- Python 데이터 분석
- Python RPA
- cython
- PyCharm
- pySide
- kivy (python)
Python 자료구조 [파이썬으로 구현한 알고리즘] (7) 트리(Tree)
2018.02.27 17:50
[파이썬으로 구현한 알고리즘] (7) 트리(Tree)
트리는 2차원적인 비선형(Non-linear structure) 구조 이다. 앞서 다루었던 연결 리스트, 스택, 큐는 처음과 끝이 있고, 차례로 처음부터 끝까지 이동하면 모든 노드를 거칠 수 있는 선형적인 구조 였다.
트리 구조의 대표 적인 예는 디렉토리 구조라고 할 수 있다. 루트 디렉토리가 있고, 그 아래에 서브 디렉토리가 그리고 그 서브 디렉토리의 서브 디렉토리가 있는 재귀적으로 구성되는 구조 이다. 
트리에 사용되는 용어는 상당히 많다. 먼저 노드(node)는 하나의 정보 항목에다가 이것으로부터 다른 노드로 뻗어진 가지를 합친것을 의미 한다. 트리는 1개 이상의 노드로 이루어진 유한 집합이다. 노드 중에는 루트(root)라고 하는 노드가 하나 있고, 나머지 노드들은 각각 분리된 분리집합을 이룰수 있다. 여기서 분리된 분리집합도 각각 하나의 트리이며, 루트의 서브트리(subtree)라고 한다.
어떤 노드의 서브트리의 수를 그 노드의 차수(degree)라고 한다. 차수가 0인 노드를 리프(leaf) 또는 단말(terminal node)라 하고 그 이외 나머지 노드들은 비단말 노드(non-terminal node)라고 한다. 서브트리를 갖는 노드는 그 서브트리 노드들의 부모(parent)이며, 서브트리 노드들은 자식(children)이라 한다. 같은 부모를 가진 자식들을 형제(sibling)라 한다.
한 노드의 조상(ancestors)은 루트 노드에서부터 그 노드에 이르는 경로상에 있는 모든 노드를 말하며, 자손(descendants)는 한 노드의 서브트리에 속한 모든 노드들을 말한다.
노드의 레벨(level)은 루트 노드를 1로 하고, 모든 노드들의 레벨은 그 부모 노드의 레벨에 1을 더한 값이다. 트리의 높이(height) 또는 깊이(depth)란 그 트리에 속한 노드의 최대 레벨을 말한다.
어떤 노드의 서브트리의 수를 그 노드의 차수(degree)라고 한다. 차수가 0인 노드를 리프(leaf) 또는 단말(terminal node)라 하고 그 이외 나머지 노드들은 비단말 노드(non-terminal node)라고 한다. 서브트리를 갖는 노드는 그 서브트리 노드들의 부모(parent)이며, 서브트리 노드들은 자식(children)이라 한다. 같은 부모를 가진 자식들을 형제(sibling)라 한다.
한 노드의 조상(ancestors)은 루트 노드에서부터 그 노드에 이르는 경로상에 있는 모든 노드를 말하며, 자손(descendants)는 한 노드의 서브트리에 속한 모든 노드들을 말한다.
노드의 레벨(level)은 루트 노드를 1로 하고, 모든 노드들의 레벨은 그 부모 노드의 레벨에 1을 더한 값이다. 트리의 높이(height) 또는 깊이(depth)란 그 트리에 속한 노드의 최대 레벨을 말한다.
이진 트리(Binary Tree)
트리 중에서 최대 차수가 2인 트리를 이진 트리(binary tree)라고 한다. 이진 트리는 트리 구조에서 실용적이고 구현이 용이해서 가장 많이 쓰인다. 이진 트리에서 자식은 왼쪽 자식(left child)와 오른쪽 자식(right child)만 가진다.
이진 트리에서 마지막 레벨을 제외한 각 레벨의 노드들이 꽉 차 있는 이진 트리를 완전한 이진 트리(complete binary tree)라고 하며, 모든 레벨이 꽉 차 있는 이진 트리를 포화 이진 트리(full binary tree)라고 한다.
이제 파이썬으로 이진 트리의 노드를 표현 해 보자.
트리를 구성하려면 다음과 같이 자식 노드를 먼저 생성하고, 부모 노드에 그것들을 연결 해야 한다.
다음과 같이 간결하게 할 수도 있다.
<그림 3>과 같은 트리를 생성하는 함수를 만들어 보자. 노드의 데이타는 왼쪽 리프 노드부터 1부터 차례대로 넣었다.
< 그림 5. init_tree()로 생성된 이진 트리 >
트리 순회(Tree Traverse)
트리에서 모든 노드를 중복 없이 순회 하는 방법에는 네가지가 있다.
각각 'print tree.data ' 위치에 따라 전위, 중위, 후위 순휘가 된다. 재귀 함수에 종료 조건이 꼭 있어야 된다는 것을 잊지 말자.
레벨 순회는 큐를 이용하여 구현 할 수있다. 먼저 부모를 방문하고, 자식들을 큐에 넣는다. 큐에서 노드를 하나 꺼내 방문하고, 그 노드가 자식을 가지고 있으면 큐에 넣는다. 이런씩으로 큐를 이용하여 레벨 순회를 구현 할 수 있다.
마지막으로 <그림 5>의 이진 트리를 생성하고, 이들을 각각 전위, 중위, 후위, 레벨 순회로 방문하는 예제를 작성 해봄으로써 트리에 대한 내용을 마무리 하겠다.
class Tree:
def __init__(self, data, left_child=None, right_child=None):
self.data = data
self.left_child = left_child
self.right_child = right_child
def __init__(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)
right_child = Tree(4)
parent = Tree(1, left_child, right_child)
다음과 같이 간결하게 할 수도 있다.
parent = TreeNode(1, TreeNode(3), TreeNode(4))
<그림 3>과 같은 트리를 생성하는 함수를 만들어 보자. 노드의 데이타는 왼쪽 리프 노드부터 1부터 차례대로 넣었다.
def init_tree():
# create leaf node
leaf = []
for i in range(6):
leaf.append( Tree(i+1) )
# create sub tree
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)
# create leaf node
leaf = []
for i in range(6):
leaf.append( Tree(i+1) )
# create sub tree
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)
트리 순회(Tree Traverse)
트리에서 모든 노드를 중복 없이 순회 하는 방법에는 네가지가 있다.
- 전위 순회(Preorder Traverse) : 뿌리를 먼저 방문 한다.
- 중위 순회(Inorder Traverse) : 뿌리를 중간에 방문 한다.
- 후위 순회(Postorder Traverse) : 뿌리를 나중에 방문 한다.
- 층별순회(Levelorder Traverse) : 레벨별로 방문 한다.
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,
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,
각각 'print tree.data ' 위치에 따라 전위, 중위, 후위 순휘가 된다. 재귀 함수에 종료 조건이 꼭 있어야 된다는 것을 잊지 말자.
레벨 순회는 큐를 이용하여 구현 할 수있다. 먼저 부모를 방문하고, 자식들을 큐에 넣는다. 큐에서 노드를 하나 꺼내 방문하고, 그 노드가 자식을 가지고 있으면 큐에 넣는다. 이런씩으로 큐를 이용하여 레벨 순회를 구현 할 수 있다.
levelq = []
def levelorder_traverse(tree):
global levelq
levelq.append(tree)
while len(levelq) != 0:
# visit
visit_node = levelq.pop(0)
print visit_node.data,
# child put
if visit_node.left_child != None:
levelq.append(visit_node.left_child)
if visit_node.right_child != None:
levelq.append(visit_node.right_child)
def levelorder_traverse(tree):
global levelq
levelq.append(tree)
while len(levelq) != 0:
# visit
visit_node = levelq.pop(0)
print visit_node.data,
# child put
if visit_node.left_child != None:
levelq.append(visit_node.left_child)
if visit_node.right_child != None:
levelq.append(visit_node.right_child)
마지막으로 <그림 5>의 이진 트리를 생성하고, 이들을 각각 전위, 중위, 후위, 레벨 순회로 방문하는 예제를 작성 해봄으로써 트리에 대한 내용을 마무리 하겠다.
#!/usr/bin/python
class Tree:
def __init__(self, data, left_child = None, right_child = None):
self.data = data
self.left_child = left_child
self.right_child = right_child
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,
levelq = []
def levelorder_traverse(tree):
global levelq
levelq.append(tree)
while len(levelq) != 0:
# visit
visit_node = levelq.pop(0)
print visit_node.data,
# child put
if visit_node.left_child != None:
levelq.append(visit_node.left_child)
if visit_node.right_child != None:
levelq.append(visit_node.right_child)
root = None
def init_tree():
global root
# create leaf node
leaf = []
for i in range(6):
leaf.append( Tree(i+1) )
# create sub tree
left_subtree = Tree(9, Tree(7, leaf[0], leaf[1]), Tree(8, leaf[2], leaf[3]))
right_subtree = Tree(10, leaf[4], leaf[5])
# create root
root = Tree(11, left_subtree, right_subtree)
def Main():
init_tree()
print "< Preorder Traverse >"
preorder_traverse(root)
print
print "< Inorder Traverse >"
inorder_traverse(root)
print
print "< Postorder Traverse >"
postorder_traverse(root)
print
print "< Leveorder Traverse >"
levelorder_traverse(root)
print
Main()
class Tree:
def __init__(self, data, left_child = None, right_child = None):
self.data = data
self.left_child = left_child
self.right_child = right_child
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,
levelq = []
def levelorder_traverse(tree):
global levelq
levelq.append(tree)
while len(levelq) != 0:
# visit
visit_node = levelq.pop(0)
print visit_node.data,
# child put
if visit_node.left_child != None:
levelq.append(visit_node.left_child)
if visit_node.right_child != None:
levelq.append(visit_node.right_child)
root = None
def init_tree():
global root
# create leaf node
leaf = []
for i in range(6):
leaf.append( Tree(i+1) )
# create sub tree
left_subtree = Tree(9, Tree(7, leaf[0], leaf[1]), Tree(8, leaf[2], leaf[3]))
right_subtree = Tree(10, leaf[4], leaf[5])
# create root
root = Tree(11, left_subtree, right_subtree)
def Main():
init_tree()
print "< Preorder Traverse >"
preorder_traverse(root)
print "< Inorder Traverse >"
inorder_traverse(root)
print "< Postorder Traverse >"
postorder_traverse(root)
print "< Leveorder Traverse >"
levelorder_traverse(root)
Main()
본 웹사이트는 광고를 포함하고 있습니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
