[자료구조] Tree 트리

트리(Tree)의 개념

트리는 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어있다. 

 

1. 트리는 하나의 루트노드를 갖는다

2. 루트 노드는 0개 이상의 자식 노드를 갖고잇다. 

3. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고있고, 이는 반복적으로 정의된다. 

 

 

 

트리와 관련된 용어 

트리의 특징 

그래프의 한 종류

최소 연결 트리

계층모델

DAG(directed acyclic graphs, 방향성이 있는 비순환 그래프)의 한 종류

트리에는 사이클이 존재할 수 없다.(loop, circuit, self-loop 전부 없음)

노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다

각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다

각 노드는 어떤 자료형으로도 표현이 가능

비선형 자료구조로 계층적 관계를 표현

노드가 N개인 트리는 항상 N-1개의 간선을 가진다

루트에서 어떤 노드로 가는 경로는 유일 (임의의 두 노드간의 경로도 유일)

한 개의 루트노드만이 존재, 모든 자식 노드는 한 개의 부모 노드만을 가짐

 

트리의 종류 

이진트리