[자료구조] 5. Tree

1. 정의

Tree 구조는 Stack, Queue와 같은 선형적인 구조가 아니라 계층적인 구조를 가지고 있다. 계층적인 자료구조의 모습이 마치 나무와 비슷하게 보여, Tree라는 이름을 가지게 되었다. 자료를 Tree 구조로 저장하기 위해서는 나무의 잎인 Node에 데이터를 저장하고, 그 Node들의 연결을 가지(Branch)인 선분으로 연결한다. Graph의 측면에서 볼때, Tree는 cycle이 존재하지 않는 graph의 특수한 형태이다.

<The Example of Tree Structure>

2. Tree 용어 정리

- Node(노드) : Tree를 구성하는 기본 원소들을 말한다.

- Root Node(루트 노드) : Tree를 구성하는 노드 중 가장 위의 노드를 일컫는다.

- Parent : 어떤 노드의 Branch로 연결된 바로 위의 노드를 말한다.

- Child : 어떤 노드의 Branch로 연결된 바로 아래의 노드를 말한다.

- Ancestor : 어떤 노드의 위로 연결된 모든 노드들을 일컫는다.

- Descendant : 어떤 노드의 아래로 연결된 모든 노드들을 일컫는다.

- Sibling : 노드들 중 Parent가 같은 노드들을 말한다.

- Leaf(=Terminal node) : Tree를 구성하는 노드 중 Child가 없는 노드를 말한다.

- Degree(차수) : 각 노드에서 뻗어나온 Branch의 수를 말한다. Tree의 Degree는 최대 차수를 말한다.

- Level : root 노드를 level 1으로 하며, 노드의 child는 항상 parent의 level보다 1 크다.

- Depth(=Height)(깊이) : Tree의 높이를 말하며, Tree에서의 최대 Level과 같다.

3. 종류

1) Binary Tree

2) Threaded Binary Tree

4. 코드