Tree

Tree

Tree는 Stack, Queue와 같은 선형 자료구조가 아닌 비선형 자료구조이다.
트리는 계층적 관계를 표현하기 위한 자료구조이다.

트리의 구성요소

• 노드 : 트리를 구성하고 있는 각각의 요소
• 간선 : 트리를 구성하기 위해 노드와 노드를 연결하는 선
• 루트 노드 : 트리구조에서 최상위 노드를 의미
• 단말 노들 : 하위에 다른 노드가 연결되어있지 않은 노드

Binary Tree(이진 트리)

루트 노드를 기준으로 두 개의 서브 트리로 나뉘어지는 트리 구조
나뉘어진 두 노드 역시 두개의 서브 트리를 갖는다.

트리에서는 각 층별로 숫자를 매겨서 이를 트리의 Level(레벨)이라고 한다. 루트 노드의 레벨은 0 이다. 그리고 트리의 최고 레벨을 가리켜 해당 트리의 height(높이)라고 한다.

배열로 구성된 Binary Tree는 노드의 개수가 n 개이고 root가 0이 아닌 1에서 시작할 때, i 번째 노드에 대해서 parent(i) = i/2 , left_child(i) = 2i , right_child(i) = 2i + 1 의 index 값을 갖는다.

Perfect Binary Tree (포화 이진 트리), Complete Binary Tree (완전 이진 트리), Full Binary Tree (정 이진 트리)

모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진 트리라고 한다. 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리라고 한다. 모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리를 가리켜 정 이진 트리라고 한다.