(자료구조) 트리의 정의 및 용어 정리 - Tree(1)

● 트리란? 
트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다. (비선형 자료구조)

 

트리(Tree)

○  트리의 구조 

1. 트리는 하나의 루트 노드를 갖는다.
2. 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
3. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.
※ 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.
    -  트리에는 사이클(cycle)이 존재할 수 없다.
    -  노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다.
    -  각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다....
    -  각노드는 어떤 자료형으로도 표현 가능하다.
    -  트리는 단순한 데이터의 저장을 넘어서 데이터의 표현을 위한 도구이다.

● 트리 관련 용어의 소개

Tree의 용어 정리

1. 노드 : node
 - 트리의 구성요소에 해당하는 데이터를 담은 요소
2. 간선 : edge
 - 노드와 노드를 연결하는 연결선
3. 루트 노드 : root
 - 트리 구조에서 최상위에 존재하는 A와 같은 노드
4. 단말 노드 : terminal node
 - 아래로 또 다른 노드가 연결되어 있지 않은 노드
5. 내부 노드 : internal node
 - 단말 노드를 제외한 모든 노드
 
(연결리스트의 노드와 의미적으로 약간 다름)
※ 트리의 노드간 관계
 1.부모노드(parent) (상위)
 2.자식노드(child)   (하위)
 3.형제노드(sibling) (동일)

● 서브 트리의 이해

서브 트리 역시 서브트리로 이뤄져 있으며, 그 서브 트리 역시  또 다른 서브 트리로 이뤄져 있다. (구조가 재귀적)

하나의 트리를 구성하는 왼쪽과 오른쪽의 작은 트리를 가리켜 서브트리라 한다.

서브트리 역시 또 다른 서브 트리를 갖는다.

서브 트리(SubTree)

 

트리에 대한 정의 및 기초적인 용어 / 개념등을 포스팅 하였고, 추후 트리의 구현과 순회에 대한 포스팅을 하도록 하겠다!