트리

 

트리의 개념

 

트리(Tree)는 이름 뜻처럼 나무를 닮은 자료구조이다.

 

- 트리는 뿌리(Root), 가지(Branch, 잎(Leaf) 처럼 세 가지로 이루어져 있다.

- 뿌리, 가지, 잎은 모두 실제로는 똑같은 노드이다.

 

 

 

 

루트는 트리 자료구조의 가장 위에 있는 노드를 가리키고, 가지는 루트와 잎 사이에 있는 모든 노드를 가리킨다. 그리고 가지의 끝에 매달려 있는 노드를 잎이라고 한다.

 

트리 용어

 

경로(Path) : 트리에서 경로는 한 노드에서부터 다른 노드까지 이르는 길 사이에 놓여있는 노드들의 순서..

길이(Length) : 출발 노드에서 목적지 노드까지 거쳐야 하는 노드의 개수..

깊이(Depth) : 루트 노드에서 해당 노드까지의 경로의 길이를 말한다.

레벨(Level) : 깊이가 같은 노드의 집합을 말한다.

높이(Height) : 트리의 높이는 가장 깊은 곳에 있는 잎 노드까지의 깊이를 뜻한다.

차수(Degree) : 노드의 차수라고 하면 그 노드의 자식 노드 개수를 말하는 것이다.

                         트리의 차수라고 하면 트리 내에 있는 노드 가운데 자식 노드가 가장 많은 노드의 차수를 말하

                         는 것이다.

 

 

트리의 표현방법

 

트리는 여러 가지 방법으로 표현이 가능한 자료구조이다.

일반적으로 거꾸로 세운 나무 모양이 가장 일반적인 트리모양이고, GUI(Graphic User Interface)로 표현되는 트리구조도 있다.

 

1. 중첩된 괄호(Nested Parenthesis) 표현법

- 이 표현법은 같은 레벨의 노드들을 괄호로 묶어 표현하는 방법이다.

 

2. 중첩된 집합(Nested Set) 표현법

- 트리가 하위 트리의 집합이라는 관계를 잘 표현할 수 있는 장점이 있는 표현법이다.

 

3. 들여쓰기 표현법(Indentation) 표현법

- 들여쓰기로 표현된 트리는 자료의 계층적인 특징을 잘 나타낸다.

- 들여쓰기의 표현법의 예로 윈도우 탐색기가 있다.

 

노드 표현하기

 

노드의 표현법이라고 하면 부모와 자식, 형제 노드를 서로 연결짓는것을 말한다.

 

 

 

트리 노드를 표현하는 방법

 

 

N - Link 표현법

- 노드의 차수가 N이라면, 노드가 N개의 링크를 가지고 있어서 이 링크들이 각각 자식의 노드를 가리키도록 노드를 구성하는 것.

- 차수가 노드마다 달라지는 트리에서는 적용하기가 어렵다.

 

Left Child - Right Child 표현법

- 왼쪽 자식과 오른쪽 형제에 대한 포인터를 갖고 있는 노드의 구조이다.

- N개의 차수를 가진 노드의 표현이 두 개의 포인터, 왼쪽 자식-오른쪽 형제만으로 가능하게 됨

- 이 표현법을 사용하는 트리에서 어느 한 노드의 모든 자식 노드를 얻으려면 일단 왼쪽 자식 노드에 대한 포인터만 있으면 된다.

이 포인터를 이용해서 왼쪽 자식 노드의 주소를 얻은 후에,, 이 자식 노드의 오른쪽 형제 노드의 주소를 얻고, 또 그 다음의 오른쪽 형제 노드의 주소를 계속 해서 얻어 나가면... 결국엔 모든 자식 노드를 얻을 수 있다..

 

 

자식 노드에 연결하기

 

1. 부모 노드가 자식 노드가 있는지 없는지를 검사

2. LeftChild가 NULL 일 때 자식의 노드가 없는 것이다.

3. 자식 노드가 없을 때는 LeftChild 포인터에 Child가 가리키고 있는 주소를 저장하면 된다.

4. 부모의 LeftChild가 NULL이 아니라는 것은 자식 노드가 하나 이상 있다는 것을 말한다.

5. 자식 노드의 RightSibling 포인터를 이용해서 가장 오른쪽에 있는 자식 노드 찾아내고,,,

  찾아낸 최우측 자식 노드의 RightSibling에 Child를 대입한다.