트리 in C#

1. 트리

 연결 리슽, 스택, 큐는 모두 선형적인 구조였다. 즉, 청므과 끝이 하나이며 차례대로 이어져 있다. 트리는 말 그대로 나무와 같은 구조이다. 하나의 뿌리에서 가지가 하나씩 뻗쳐나가는 구조로 이차원적인 구조이다. 토너먼트 대진표와 군대 서열 등이 대표적인 예이다. 트리는 노드(node)라는 항목들이 계층적으로 배치되어 구성되나. 계층의 최상위 노드를 루트(root)라고 한다. 루트 바로 아래의 노드들은 루트의 자식들(children)이며 이런 자식 노드들 아래에 도 자식이 생긴다. 부모가 가질 수 있는 자식의 수는 트리의 형태에 따라 달라진다.

 

1.1 이진트리

 이진트리는 자식을 두개까지만 가질 수 있는 노드로 이러우진 트리를 말한다. 

 

 

1.1.1 순회

 순회란 이진 트리의 노드들을 중복되지 않게 한번씩 검색하는 방법이다. 선형 구조가 아니므로 이진 트리의 순회 방법은 분명해 보이지 않을 수도 있다. 

순회 방법은 크게 전위 순회, 중위 순회, 후위 순회, 단계 순위 순회가 있다. 

루트를 기준으로 생각하면 순회는 생각하기 쉽다.

 

(1)전위순회 rLR

 

재귀호출 이용

 

 

 

(2)중위순회 LrR

위의 코드에서 순서만 바꾸면 된다. 

 

Traversal(cur.left);

Console.WriteLine("{0}", cur);

Traversal(cur.right);

 

(3)후위순회 LRr

위의 코드에서 순서만 바꾸면 된다. 

 

Traversal(cur.left);

Traversal(cur.right);

Console.WriteLine("{0}", cur);