트리 순회( tree traversal ) 순회 방법

• 트리 순회( tree traversal )는 트리 구조에서 각각의 노드를 한 번씩만 체계적으로 방문하는 과정을 말합니다. 그리고 노드를 순회하는 순서에 따라서 후위 순회, 전위 순회, 중위 순회가 있습니다.

후위 순회( postorder traversal )

• 후위 순회(postorder traversal)는 자식들 노드를 방문하고 자신의 노드를 방문하는 것을 말합니다.

후위 순회 pseudo code

postorder( node )
    if (node.visited == false)
        postorder( node->left )
        postorder( node->right )
        node.visited = true

전위 순회( preorder traversal )

• 전위 순회( preorder traversal )는 먼저 자신의 노드를 방문하고 그 다음 자식 노드들을 방문하는 것을 말합니다.

전위 순회 pseudo code

preorder( node )
    if (node.visited == false)
        node.visited = true
        preorder( node->left )
        preorder( node->right )

중위 순회( inorder traversal )

• 중위순회(inorder traversal)는 왼쪽 자식 노드를 먼저 방문 그다음의 자신의 노드를 방문하고 그 다음 오른쪽 자식 노드를 방문하는 것을 말합니다.

• 이진 탐색 트리에서 오름 차순으로 접근할 때 중위 순회를 사용합니다.

중위 순회 pseudo code

inorder( node )
    if (node.visited == false)
        inorder( node->left )
        node.visited = true
        inorder( node->right )