트리 순회

정의

 자료 구제에 저장된 모든 데이터를 출력

 출력하고자 하는 트리의 루트노드를 파라미터로 받음

 

동작

 1. 재귀적으로 왼쪽 부분 트리 순회

     루트의 왼쪽만 출력

def traverse(node):
	traverse(node.left_child)

     

 2. 재귀적으로 오른쪽 부분 트리 순회

     루트의 오른쪽만 출력

def traverse(node):
	traverse(node.right_child)

 3. 현재 노드를 출력

     노드의 data로 접근

def traverse(node):
	print(node.data)

pre-order 순회(두개의 부분 트리를 순회하기 전에 노드를 출력하는 방식)

 동작방식

  1. 현재 노드를 출력

  2. 재귀적으로 왼쪽 부분 트리 순회 - 순서는 왼쪽자식에서 오른쪽 자식

  3. 재귀적으로 오른쪽 부분 트리 순회

* F, B, A, D, C, E, G, I, H

post-order 순회(부분 트리를 순회한 후에 노드를 출력하는 방식)

 동작방식

  1. 루트노드의 왼쪽을 재귀적으로 왼쪽 부분 트리 순회

  2. 루트노드의 오른쪽을 재귀적으로 오른쪽 부분 트리 순회

  3. 현재 노드를 출력

* A, C, E, D, B, H, I, G, F

in-order 순회

 동작방식

  1. 루트노드의 왼쪽을 재귀적으로 왼쪽 부분 트리 순회

  2. 현재 노드를 출력

  3. 루트노드의 오른쪽을 재귀적으로 오른쪽 부분 트리 순회

* A, B, C, D, E, F, G, H, I

구현

# 재귀를 이용한 in-order 트리순회
class Node:
    """이진 트리 노드를 나타내는 클래스"""

    def __init__(self, data):
        """이진 트리 노드는 데이터와 두 자식 노드에 대한 레퍼런스를 갖는다"""
        self.data = data
        self.left_child = None
        self.right_child = None

def traverse_inorder(node):
    """in-order 순회 함수"""
    if node is not None:
        traverse_inorder(node.left_child)  # 재귀적으로 왼쪽 부분 트리 순회
        print(node.data)  # 데이터 출력
        traverse_inorder(node.right_child)  # 재귀적으로 오른쪽 부분 트리 순회
    # if node.left_child is not None:
    #     left_node = node.left_child
    #     traverse_inorder(left_node)
  
    # print(node.data)

    # if node.right_child is not None:
    #     right_node = node.right_child
    #     traverse_inorder(right_node)


# 여러 노드 인스턴스 생성
node_A = Node("A")
node_B = Node("B")
node_C = Node("C")
node_D = Node("D")
node_E = Node("E")
node_F = Node("F")
node_G = Node("G")
node_H = Node("H")
node_I = Node("I")

# 생성한 노드 인스턴스들 연결
node_F.left_child = node_B
node_F.right_child = node_G

node_B.left_child = node_A
node_B.right_child = node_D

node_D.left_child = node_C
node_D.right_child = node_E

node_G.right_child = node_I

node_I.left_child = node_H

# 노드 F를 root 노드로 만든다
root_node = node_F

# 만들어 놓은 트리를 in-order로 순회한다
traverse_inorder(root_node)