Tree 란?
트리(Tree)란 노드들이 나무가지처럼 연결된 비선형 계층적 자료구조다.
트리는 다음과 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사하다.

트리 구조에서 사용되는 기본 용어

- 노드(Node)
- 트리를 구성하고 있는 기본요소.
- 노드에는 키 or 값과 하위 노드에 대한 포인터를 가지고 있다.
- A, B, C, D, E, F, G, H, I, J
- 간선(Edge)
- 루트 노드(Root Node)
- 트리 구조에서 부모가 없는 최상위 노드
- root node: A
- 부모 노드(Parent Node)
- 자식 노드를 가진 노드.
- H, I에 부모 노드는 D.
- 자식 노드(Child Node)
- 부모 노드의 하위 노드.
- 노드 D의 자식 노드는 H, I
- 형제 노드(Sibling Node)
- 같은 부모를 가진 노드.
- H, I는 같은 부모를 가지는 형제 노드
- 외부 노드(External Node, Outer Node), 단말 노드(Terminal Node), 리프 노드(Leaf Node)
- 자식 노드가 없는 노드.
- H, I, J, F, G
- 내부 노드(Internal Node, Inner Node), 비단말 노드(Non-terminal Node), 가지 노드(Branch Node)
- 자식 노드 하나 이상 가진 노드.
- A, B, C, D, E
- 깊이(Depth)
- 루트에서 어떤 노드까지의 간선(Edge) 수
- 루트 노드의 깊이: 0.
- D의 깊이: 2
- 높이(Height)
- 어떤 노드에서 리프 노드까지의 가장 긴 경로의 간선(Edge) 수.
- 리프 노드의 높이: 0
- A 노드의 높이: 3