이진 트리를 순회하는 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]