Python 자료구조 [파이썬으로 구현한 알고리즘] (7) 트리(Tree)

2018.02.27 17:50

졸리운_곰 조회 수:1957

경축! 아무것도 안하여 에스천사게임즈가 새로운 모습으로 재오픈 하였습니다.
어린이용이며, 설치가 필요없는 브라우저 게임입니다.
https://s1004games.com

[파이썬으로 구현한 알고리즘] (7) 트리(Tree)

        
 
 트리는 2차원적인 비선형(Non-linear structure) 구조 이다. 앞서 다루었던 연결 리스트, 스택, 큐는 처음과 끝이 있고, 차례로 처음부터 끝까지 이동하면 모든 노드를 거칠 수 있는 선형적인 구조 였다.
 트리 구조의 대표 적인 예는 디렉토리 구조라고 할 수 있다. 루트 디렉토리가 있고, 그 아래에 서브 디렉토리가 그리고 그 서브 디렉토리의 서브 디렉토리가 있는 재귀적으로 구성되는 구조 이다.
 
사용자 삽입 이미지
< 그림 1. 트리 구조 >
 
 트리에 사용되는 용어는 상당히 많다. 먼저 노드(node)는 하나의 정보 항목에다가 이것으로부터 다른 노드로 뻗어진 가지를 합친것을 의미 한다. 트리는 1개 이상의 노드로 이루어진 유한 집합이다. 노드 중에는 루트(root)라고 하는 노드가 하나 있고, 나머지 노드들은 각각 분리된 분리집합을 이룰수 있다. 여기서 분리된 분리집합도 각각 하나의 트리이며,  루트의 서브트리(subtree)라고 한다.
 어떤 노드의 서브트리의 수를 그 노드의 차수(degree)라고 한다. 차수가 0인 노드를 리프(leaf) 또는 단말(terminal node)라 하고 그 이외 나머지 노드들은 비단말 노드(non-terminal node)라고 한다. 서브트리를 갖는 노드는 그 서브트리 노드들의 부모(parent)이며, 서브트리 노드들은 자식(children)이라 한다. 같은 부모를 가진 자식들을 형제(sibling)라 한다.
 한 노드의 조상(ancestors)은 루트 노드에서부터 그 노드에 이르는 경로상에 있는 모든 노드를 말하며, 자손(descendants)는 한 노드의 서브트리에 속한 모든 노드들을 말한다.
 노드의 레벨(level)은 루트 노드를 1로 하고, 모든 노드들의 레벨은 그 부모 노드의 레벨에 1을 더한 값이다. 트리의 높이(height) 또는 깊이(depth)란 그 트리에 속한 노드의 최대 레벨을 말한다.

사용자 삽입 이미지
< 그림 2. 트리에서 쓰이는 용어 >
 

이진 트리(Binary Tree)

 트리 중에서 최대 차수가 2인 트리를 이진 트리(binary tree)라고 한다. 이진 트리는 트리 구조에서 실용적이고 구현이 용이해서 가장 많이 쓰인다. 이진 트리에서 자식은 왼쪽 자식(left child)와 오른쪽 자식(right child)만 가진다.
 이진 트리에서 마지막 레벨을 제외한 각 레벨의 노드들이 꽉 차 있는 이진 트리를 완전한 이진 트리(complete binary tree)라고 하며, 모든 레벨이 꽉 차 있는 이진 트리를 포화 이진 트리(full binary tree)라고 한다.
 
사용자 삽입 이미지
< 그림 3. 완전한 이진 트리 >
 
사용자 삽입 이미지
< 그림 4. 포화 이진 트리 >
 
이제 파이썬으로 이진 트리의 노드를 표현 해 보자.
 
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

트리를 구성하려면 다음과 같이 자식 노드를 먼저 생성하고, 부모 노드에 그것들을 연결 해야 한다.
 
left_child = Tree(3)
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)
 
사용자 삽입 이미지
< 그림 5. init_tree()로 생성된 이진 트리 >


트리 순회(Tree Traverse)

 트리에서 모든 노드를 중복 없이 순회 하는 방법에는 네가지가 있다.
  • 전위 순회(Preorder Traverse) : 뿌리를 먼저 방문 한다.
  • 중위 순회(Inorder Traverse) : 뿌리를 중간에 방문 한다.
  • 후위 순회(Postorder Traverse) : 뿌리를 나중에 방문 한다.
  • 층별순회(Levelorder Traverse) : 레벨별로 방문 한다.
<그림 5>의 이진 트리를 순회하는 전위, 중위, 후위 순회는 다음과 같은 재귀함수로 간단히 구현 할 수 있다.
 
 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,

 각각 '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)

마지막으로 <그림 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()


 
[출처] http://onestep.tistory.com/42
본 웹사이트는 광고를 포함하고 있습니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
이 게시물을
목록
목록
쓰기
태그
대표 김성준 주소 : 경기 용인 분당수지 U타워 등록번호 : 142-07-27414
통신판매업 신고 : 제2012-용인수지-0185호 출판업 신고 : 수지구청 제 123호 개인정보보호최고책임자 : 김성준 sjkim70@stechstar.com
대표전화 : 010-4589-2193 [fax] 02-6280-1294 COPYRIGHT(C) stechstar.com ALL RIGHTS RESERVED