Binary Tree Traversal, Binary Tree

Leetcode의 문제를 풀려고 설명을 읽던 중 inorder traversal 이란 단어에서 막혔다. 몇몇 Tree 문제를 풀었는데도, 처음 보는 단어가 튀어 나와 공부할게 생겼다. traversal이란 Binary Tree 자료 구조의 모든 노드를 방문할 수 있는 방법이다. 선형 자료 구조 (연결 리스트, 스택, 큐 등)은 순차적으로 접근하지만 Tree 자료 구조의 접근 방식은 다르다.

 

보통 Tree에서는 Depth First Search (DFS), Breadth Frist Search (BFS)를 사용해 노드 순회 및 탐색이 가능하다. Binary Tree인 경우 위 두 방법과 함께 Recursion 방법을 사용해 순회 및 탐색이 가능하다.

 

DFS로 Tree를 순회할 경우, Queue를 활용하면 된다. BFS를 사용할 경우 Stack을 활용하면 된다. Binary Tree를 Recursion으로 순회할 경우에는 특별한 데이터 구조가 필요하진 않다.

 

Tree Traversal (트리 순회) 종류

Binary Tree는 1개의 부모 노드에 2개의 자식 노드가 있는 구조이다. 부모 노드와 자식 노드의 방문 순서에 따라 3가지의 Tree Traversal 종류가 있다.

 

1. Preorder Traversal (전위 순회)
2. Inorder Traversal (중위 순회)
3. Postorder Traversal (후위 순회)

 

Preorder Traversal

부모 노드를 방문 후, 왼쪽 Sub Tree를 순회한 후 오른쪽 Sub Tree를 순회한다.

• 부모 노드 방문
• 왼쪽 Sub Tree Preorder Traversal
• 오른쪽 Sub Tree Preorder Traversal

방문 순서 : A - B - C - D - E - F - G - H - I

Tree의 DFS 탐색 결과와 동일하다.

 

Inorder Traversal

왼쪽 Sub Tree를 순회한 후, 부모 노드를 방문하고 오른쪽 Sub Tree를 순회한다.

• 왼쪽 Sub Tree Inorder Traversal
• 부모 노드 방문
• 오른쪽 Sub Tree Inorder Traversal

방문 순서 : C - B - E - D - F - A - G - I - H

 

Postorder Traversal

왼쪽 Sub Tree를 순회한 후, 오른쪽 Sub Tree를 순회하고 부모 노드를 방문한다.

• 왼쪽 Sub Tree Postorder Traversal
• 오른쪽 Sub Tree Postorder Traversal
• 부모 노드

방문 순서 : C - E - F - D - B - I - H - G - A

 

세가지 순회 방법 모두 왼쪽을 오른쪽보다 먼저 순회한다는 특징이 있다.

 

Code.

void TreeTraversal(* Node)
{
	if(Node != nullptr)
    {
        // VisitNode(Node);   preorder
        TreeTraversal(Node->left);
        // VisitNode(Node);   inorder
        TreeTraversal(Node->right);
        // VisitNode(Node);   postorder
    }
    else
    {
    	// Do Nothing
    }
}

 

 

Leet Code

관련 문제를 풀어보고 싶으면 Leet Code 95 번 문제를 참고하면 된다.

 

 

Reference

1. https://gnujoow.github.io/ds/2016/09/01/DS4-TreeTraversal/