트리의 순회 (pre, in, post order)

이진 트리를 순회하는 3가지 방식에 대해 알아보자.

트리의 모양

먼저 순회할 트리의 모양은 다음과 같다.

from collections import deque
      
class Node:
  def __init__(self, data, left = None, right = None):
    self.data = data
    self.left = left
    self.right = right
    
class Tree:
  L, R = 'left', 'right'
  def __init__(self, rootVal):
    self.rootNode = Node(rootVal)
    
  def insert(self, val):
    emptyNode = self.findEmptyNode()
    if emptyNode[1] == Tree.L: emptyNode[0].left = Node(val)
    else: emptyNode[0].right = Node(val)
  
  def findEmptyNode(self):
    Q = deque([self.rootNode])
    while(len(Q) > 0):
      node = Q.popleft()
      if node.left is None: return (node, Tree.L)
      elif node.right is None: return (node, Tree.R)
      else: Q.extend([node.left, node.right])


arr = [1, 2, 3, 4, 5, 6, 7]
myTree = Tree(arr[0])
for i in range(1, len(arr)): myTree.insert(arr[i])

Preorder

preorder는 DFS랑 똑같다. 부모 노드가 앞(pre)에 온다

class Preorder:
  
  def __init__(self, tree):
    self.tree = tree
    self.result = []
  
  def start(self):
    self.traversal(self.tree.rootNode)
  
  def traversal(self, node):
    if node is None: return
    self.result.append(node.data)
    self.traversal(node.left)
    self.traversal(node.right)
    
  def print(self): print(self.result)
    

preorder = Preorder(myTree)
preorder.start()
preorder.print() # [1, 2, 4, 5, 3, 6, 7]

Inorder

inorder는 부모 노드가 가운데(in)에 배치된다.

class Inorder:
  
  def __init__(self, tree):
    self.tree = tree
    self.result = []
  
  def start(self):
    self.traversal(self.tree.rootNode)
    
  def traversal(self, node):
    if node is None: return
    self.traversal(node.left)
    self.result.append(node.data)
    self.traversal(node.right)
    
  def print(self): print(self.result)
    
    
inorder = Inorder(myTree)
inorder.start()
inorder.print() # [4, 2, 5, 1, 6, 3, 7]

Postorder

postorder는 부모가 뒤(post)에 배치된다

이진 트리를 순회하는 3가지 방식에 대해 알아보자.

트리의 모양

먼저 순회할 트리의 모양은 다음과 같다.

from collections import deque
      
class Node:
  def __init__(self, data, left = None, right = None):
    self.data = data
    self.left = left
    self.right = right
    
class Tree:
  L, R = 'left', 'right'
  def __init__(self, rootVal):
    self.rootNode = Node(rootVal)
    
  def insert(self, val):
    emptyNode = self.findEmptyNode()
    if emptyNode[1] == Tree.L: emptyNode[0].left = Node(val)
    else: emptyNode[0].right = Node(val)
  
  def findEmptyNode(self):
    Q = deque([self.rootNode])
    while(len(Q) > 0):
      node = Q.popleft()
      if node.left is None: return (node, Tree.L)
      elif node.right is None: return (node, Tree.R)
      else: Q.extend([node.left, node.right])


arr = [1, 2, 3, 4, 5, 6, 7]
myTree = Tree(arr[0])
for i in range(1, len(arr)): myTree.insert(arr[i])

Preorder

preorder는 DFS랑 똑같다. 부모 노드가 앞(pre)에 온다

class Preorder:
  
  def __init__(self, tree):
    self.tree = tree
    self.result = []
  
  def start(self):
    self.traversal(self.tree.rootNode)
  
  def traversal(self, node):
    if node is None: return
    self.result.append(node.data)
    self.traversal(node.left)
    self.traversal(node.right)
    
  def print(self): print(self.result)
    

preorder = Preorder(myTree)
preorder.start()
preorder.print() # [1, 2, 4, 5, 3, 6, 7]

Inorder

inorder는 부모 노드가 가운데(in)에 배치된다.

class Inorder:
  
  def __init__(self, tree):
    self.tree = tree
    self.result = []
  
  def start(self):
    self.traversal(self.tree.rootNode)
    
  def traversal(self, node):
    if node is None: return
    self.traversal(node.left)
    self.result.append(node.data)
    self.traversal(node.right)
    
  def print(self): print(self.result)
    
    
inorder = Inorder(myTree)
inorder.start()
inorder.print() # [4, 2, 5, 1, 6, 3, 7]

Postorder

postorder는 부모가 뒤(post)에 배치된다

class Postorder:
  
  def __init__(self, tree):
    self.tree = tree
    self.result = []
  
  def start(self):
    self.traversal(self.tree.rootNode)
    
  def traversal(self, node):
    if node is None: return
    self.traversal(node.left)
    self.traversal(node.right)
    self.result.append(node.data)
    
  def print(self): print(self.result)
    

postorder = Postorder(myTree)
postorder.start()
postorder.print() # [4, 5, 2, 6, 7, 3, 1]

Leave a Reply

Your email address will not be published.