4. 트리 Tree

        Tree란?

• 자료의 계층적 성질의 도식화
• 조직도, 토너먼트, 카테고리, etc.
• acyclic, undirected, connected graph를 의미한다.
• graph : 노드와 노드들을 연결하는 edge로 구성된 자료.
• ayclic : 노드들 사이에서 서로 순환하는 고리가 없는 것.
• undirected : 간선에 방향이 없는 것.
• connected : 모든 노드들이 전부 연결되어 있는 것.
• 위 세 가지 조건을 모두 만족해야, 트리라고 할 수 있다.

        Rooted Tree - Tree Data Structure (자료구조에서의 Tree)

• 루트가 있는 트리 : 트리구조를 노드와 간선의 집합으로 표현한 것.
• 일반적인 트리는 루트가 없지만, 자료구조에서는 대체로 루트가 있는 트리를 말한다.
• Tree와 Rooted Tree의 차이점
  Rooted Tree는 한 노드가 루트로 지정되어야한다. 그리고 이로 인해 방향성이 정해진다.
  이로 인해, undirected는 충족되지 않는다.
• Rooted Tree는 그러면 트리인가?
  1) 방향성이 있기 때문에 트리가 아니다.
  2) 트리는 트리이지만 루트가 하나 있을 뿐이다.
  1), 2) 두 가지 모두 가능!

        Tree Terminology

• 노드 node : root node와 node로 구성되어있음.
• 간선 edge : 두 노드 사이의 연결
• 부모 노드 parent : 노드 X의 부모 노드는 X와 간선으로 연결된 노드 중 루트에 더 가까운 노드
• 자식 노드 child : 노드 X의 자식 노드는 X와 간선으로 연결된 노드 중 루트에서 더 멀리 있는 노드
• 단말 노드 leaf node : 자식이 없는 노드
  *루트 노드만 하나 있을 땐?
  정의에 따라 루트 노드도 단말 노드가 된다.
• 내부 노드 internal node : 단말 노드가 아닌 노드
  *루트 노드만 하나 있을 땐?
  정의에 따라 루트 노드는 내부 노드가 될 수 없다.
• 조상 노드 Ancestor : 부모 노드는 조상 노드, 조상 노드의 부모 노드 역시 조상 노드
• 자손 노드 Descendant : 자식 노드는 자손 노드, 자손 노드의 자식 노드 역시 자손 노드
• 노드의 깊이 Depth of a node : 루트 노드와의 거리(루트 노드의 깊이는 0)
• 레벨 level : 깊이가 같은 노드들의 집합
• 트리의 높이 height : 노드의 최대 깊이
• 서브 트리 subtree : 한 노드와 그 노드의 모든 자손 노드를 포함하는 트리