이진트리의 순회 (Traversal) - 깊이 우선 순회 (DFT)

깊이 우선 순회 (Depth First Traversal)

• 중위 순회 (in-order travelsal) : 왼쪽 서브트리를 순회한 뒤 노드 x를 방문, 그리고 나서 오른쪽 서브트리를 순회
• 전위 순회 (pre-order travelsal) : 노드 x를 방문한 후에 왼쪽 서브트리를 순회, 마지막으로 오른쪽 서브트리를 순회
• 후위 순회 (post-order traversal) : 왼쪽 서브트리를 순회, 오른쪽 서브트리를 순회 후 마지막으로 노드 x를 방문

 

class Node:

    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal


    def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal
        
        
        
    def postorder(self):
        traversal = []
        if self.left:
            traversal += self.left.postorder()
        
        if self.right:
            traversal += self.right.postorder()
            
        traversal.append(self.data)
        return traversal


class BinaryTree:

    def __init__(self, r):
        self.root = r


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []
            
            
    def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []

def solution(x):
    return 0