[c++] 트리(tree)

[트리 개념]

• 각각의 자료들을 계층적으로 서로 연결한 것을 말한다.
• 주로 자료들 간의 포함 관계나 상,하위 관계를 표현할 때 사용한다.

 

[트리 용어]

• 노드 (node)  : A, B와 같은 정점
• 간선 (edge) : 노드와 노드를 잇는 선
• 근노드 (root node)  : 가장 위에 있는 뿌리와 같은 노드
• 단노드 (leaf node) : 가장 밑에 있어 자식이 없는 이파리와 같은 노드
• 부모노드 (parent node) : E의 부모노드는 B
• 자식노드 (child node) : B의 자식노드는 D와 E
• 서브 트리 (sub tree) : B의 서브 트리는 D, I, J를 가지고 있는 왼쪽과 E, K를 가지고 있는 오른쪽
• 형제노드 (sibling node) : F, G, H는 부모가 같은 형제노드
• 차수 (degree) : C의 차수는 3개
• 깊이 (depth) : 그 노드의 도달하기 까지 이어진 간선의 수
• 레벨 (level) : 위에서 부터 레벨의 수는 증가함
• 높이 (height) : 근노드부터 가장 아래에 있는 노드에 도달할 때까지 이어진 간선의 수 

 

 

[이진 트리]

• 루트를 포함한 모든 노드가 최대 2개의 자식 노드를 가질 수 있는 자료 구조이다.

이진 트리

 

 

[이진 트리 종류]

• 포화 이진 트리 : 빈 노드 없이 완벽한 피라미드를 이루는 트리
• 완전 이진트리 : 오른쪽 부터 노드가 비어있는 트리
• 편향 이진트리 : 한쪽으로 편향(치우쳐진) 트리

 

 

[이진 트리의 순회]

• 순회 : 모든 노드를 정해진 순서에 따라 한 번씩 방문하는 것

 

 

 

ex)