Tree

트리는 노드로 구성된 계층적 자료구조입니다. 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 트리 구조를 구현할 수 있습니다.

Tree 구조와 관련하여 반드시 알아야 할 개념

• A, B, C, D 등 트리의 구성요소를 노드(node) 라고 합니다.
  • 트리는 노드들의 집합으로 트리를 구성하는 것으로 보통 (value) 값과 부모 자식의 정보를 가지고 있다.
• 위 그림의 A처럼, 트리 구조에서 최상위에 존재하는 노드를 root라고 합니다.
  • 가장 상위 노드로 부모를 가지지 않는다.
• 루트를 기준으로, 다른 노드로의 접근하기 위한 거리를 depth 라고 합니다.
  • tree에서 부모에서 자식순으로 이동할 때, depth 가 1 증가하며 따라 형제 노드 간의 depth는 일치하며 root node의 depth는 0이된다.
• 같은 부모를 가지면서 같은 depth에 존재하는 노드들은 sibling 관계에 있습니다.
• 그림에서 A는 B와 C의 부모(parent) 이고, B와 C는 A의 자식(child) 입니다.
• 노드와 노드를 잇는 선을 edge 라고 합니다.
  • 엣지는 노드들을 연결하는 간선으로 부모 노드와 자식 노드를 연결하게 된다.
• 자식이 없는 노드는 leaf 라고 합니다.
  • 가장 하위 노드로 자식을 가지지 않는다.

Tree의 구현 방법

기본적으로 트리는 그래프의 한 종류이므로 그래프의 구현 방법(인접 리스트 또는 인접 배열)으로 구현할 수 있다.

인접 배열 이용

• 1차원 배열에 자신의 부모 노드만 저장하는 방법
  • 트리는 부모 노드를 0개 또는 1개를 가지기 때문
  • 부모 노드를 0개: 루트 노드
• 이진 트리의 경우, 2차원 배열에 자식 노드를 저장하는 방법
  • 이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리이기 때문
  • Ex) A[i][0]: 왼쪽 자식 노드, A[i][1]: 오른쪽 자식 노드

인접 리스트 이용

• 가중치가 없는 트리의 경우
  • ArrayList< ArrayList > list = new ArrayList<>();
• 가중치가 있는 트리의 경우
  • class Node { int num, dist; // 노드 번호, 거리 } 정의
  • ArrayList[] list = new ArrayList[정점의 수 + 1];

그래프(Graph)와 Tree(트리)의 차이

Tree(트리) method 구현

출처