[알고리즘] 트리(Tree) / 이진트리(Binary Tree) / 트리순회(Tree traversal) 개념 정리

안녕하세요 감자코딩에 감자개발자입니다^^ 오랜만에 포스팅을 하는데요. 오늘 알아볼 알고리즘개념은 트리 입니다. 자료구조론에서 가장 기본중에 기본이면서 중요한 개념을 살펴보도록 하겠습니다.

* 트리(Tree)란?

• 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다.
• 회로(cycle)가 존재하지 않는다.(사이클이 없는 그래프)
• 모든 노드는 서로 연결되어 있다.
• 정점의 개수(Vertex)
• 간선의 개수 (Vertex - 1)
• 엣지(edge)를 하나 자르면 트리가 두 개로 분리된다.
• 엣지(edge)의 수 |E$\mathrm{<span\; style="font-family:\; "Arial\; Black";\; color:\; rgb(0,\; 0,\; 0);">E</span>}$| 는 노드의 수 |V$\mathrm{<span\; style="font-family:\; "Arial\; Black";\; color:\; rgb(0,\; 0,\; 0);">V</span>}$|에서 1을 뺀 것과 같다.

* 트리 구조에서의 용어 정리 

(1). 노드(Node)

보통 데이터 트리 구조에서의 하나의 데이터들이 하나의 영역을 차지하는 곳을 노드라고 한다.

(2). 엣지(Edge)

노드와 노드사이를 이어주는 선을 엣지라고한다. 노드와의 관계를 표시 한다.

(3).경로(Path)

엣지로 연결된, 즉 인접한 노드들로 이루어진 하나의 시퀀스를 뜻한다.

(4).경로의 길이(Length)

경로에 속한 엣지(Edge)의 수를 나타낸다.

(5).트리의 높이(height)

루트노드에서 말단노드에 이르는 가장 긴 경로의 엣지 수

(6). 트리의 레벨(level)

트리의 특정 깊이를 가지는 노드의 집합을 레벨(level)이라 부릅니다.

(7). 잎새노드(leaf node)

자식노드가 없는 노드

(8). internal node

잎새노드를 제외한 노드를 나타낸다.

(9). 루트노드(root node)

부모노드가 없는 노드를 가리킵니다.

* 이진 트리(Binaray Tree)란?

이진트리란? 자식노드의 최대 개수가 2개의 노드로 구성된 트리 

이진트리의 종류 

(1) 정이진트리(full banary tree) 

- 모든 레벨의 트리에서 노드들이 모두 꽉채워진 트리

(2) 완전 이진트리(complete binary tree)

- 마지막 노드를 제외한 모든 노드들이 꽉채워진 트리 

(3) 균형 이진트리(balanced binary tree)

-모든 잎새노드와의 깊이차이가 많아야 1인 트리

이진트리의 경우 배열로 처리 할 수 있는데,

예를 들어, 부모노드가 N 이라고 하였을때 그 자식들의 노드의 인덱스는 

Left Node = 2 * N

Right Node = 2 * N  + 1

로 배열인덱스의 규칙을 띄고 있는것을 알 수 있다.

* 트리 순회(Tree Traversal)

(1) 트리 순회란?

- 트리의 모든 노드를 방문하는 순서를 나타내는 것

- 그래프(DFS,BFS)의 종류가 있다.

- 전위순회(preorder) 중위순회(inorder) 후위순회(postorder)

(2) 트리 순회 종류

예시 그래프 

지금 현재 그래프에 4 3 2 1 5 순으로 들어간 그래프가 있다는 가정으로 preorder,inorder,postorder를 풀어보도록 하겠습니다.

- preorder(전위)

루트노드 기준으로 맨처음 방문하는 순회방식중 하나로서 

Root Node - Left Child - Right Child 순서를 띄고 있습니다.

과정)

맨위에 루트노드인 4를 가장먼저 방문하고 그다음 왼쪽 자식(3) 오른쪽 자식(2) 순으로 방문하게 됩니다.

그리고나서 ,다시 3을 RootNode로 보고, 순회를 시작합니다. 그러면 3을 방문하고 1, 5를 차례대로 방문하게 됩니다.

결과) 

4 3 2 1 5

- inorder

루트노드 기준으로 중간에 방문하는 순회 방식중 하나입니다. 

Left Child - Root Node - Right Child 순서입니다.

과정)

루트노드(4)로 부터 시작하여 왼쪽 자식(3) 오른쪽 자식(2)을 탐색합니다. 왼쪽 자식에 대한 자식노드가 또 존재하므로 가장 왼쪽에 있는 Left Child(1) 부터 방문을 시작하게 됩니다. 그 이후에 1의 부모노드인 3(Root Node)을 방문하고 마지막으로 5(Right Node)를 방문하게 됩니다. 그리고 위로 올라가면서 방문하지 않는 노드를 기준(4)를 기준으로 순회를 다시 시작합니다. 3(Left Child)는 이미 방문되었으므로 그다음에 Root Node인 (4)를 방문하게 됩니다. 그리고 마지막으로 2(Right Child)를 방문하게 되므로 순회를 마치게 됩니다.

결과)

1 3 5 4 2 

- postorder

루트노드 기준으로 마지막에 방문하는 순회 방식중 하나입니다. 

Left Child - Right Child - Root Node 순서입니다.

과정) 

4를 루트 노드로 기준을 삼고, 거기에 왼쪽 자식인 3(Root Node)을 기준으로 순회 기준을 잡습니다.

가장먼저 왼쪽 자식인 1(Left Child)을 방문하고 오른쪽자식인 5(Right Child)를 방문하게 됩니다. 그리고 루트인 3(Root Node)을 방문합니다. 이제 위로 올라오면서 4(루트노드 기준)으로 왼쪽 자식인 3은 이미 방문하였으므로 Right Child인 2를 방문하게 됩니다. 그리고 Root Node 4를 방문하게 되므로 트리 순회가 종료 하게됩니다.

결과) 1 5 3 2 4

- 응용 

사칙연산 예로 (A + B ) X ( C + D) + 2 이런식으로 전위 후위 중위표기법으로 사용 할 수 있습니다.

- 마무리 

지금 까지 트리(Tree) / 이진트리(Binary Tree) / 트리순회(Tree traversal)을 알아보았습니다.

부족하지만 긴글 읽어주셔서 감사합니다. 감자 코딩에 감자개발자 였습니다.

reference: (https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/)