TREE

정점(NODE)과 선분(BRANCH) 을 이용하여 데이터의 각 요소들을 계층적으로 연관되도록 구조화 시키고자할 때 사용하는 비선형 자료구조

• 트리는 하나의 루트 노드를 갖음.
• 루트 노드는 0개 이상의 자식 노드를 가진다.
• 자식 노드 또한 0개 이상의 자식 노드를 가지며, 반복적으로 트리 구성
• 각 노드들은 서로를 연결하는 BRANCH 로 이어져있다.
• 노드가 N개인 트리는 항상 N-1개의 BRANCH를 가진다.

• 트리에는 사이클이 존재하지 않는다. (임의의 두 노드 간 경로가 유일)
• 트리는 그래프의 한 종류로 최소 연결 트리라고도 불린다.

• 사이클이 없는 하나의 연결 그래프
  -> 즉, 루트노드에서 시작하여 같은 방향으로 다시 루트노드에 도착할 수 없다.
• DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류.

DEGREE(차수)

각 노드에서 뻗어나온 가지 수
A DEGREE = 2, C DEGREE = 3

TREE의 DEGREE : DEGREE 중 가장 많은 수 = 2
TREE DEPTH = 4

순회

너비우선탐색 : BFS(Breadth First Search)

• 레벨 순회 방식
• 트리 전체를 탐색하되, 인접한 노드들을 차례대로 방문하도록 구현
• 트리의 레벨이 가장 낮고 왼쪽의 노드 부터 순서대로 방문
• 큐 자료구조를 활용하면 구현이 편리하다.

깊이우선탐색 : DFS(Depth First Search)

전위 순회(Preorder Traversal)

1. 루트노드 방문
2. 왼쪽 서브트리를 전위 순회
3. 오른쪽 서브트리를 전위 순회

위 트리의 전위 순회 결과는 A->B->C->D->E->F->G

중위 순회(Inorder Traversal)

1. 왼쪽 서브트리를 중위 순회
2. 루트노드 방문
3. 오른쪽 서브트리를 중위 순회
   위 트리의 중위 순회 결과는 D->B->E->A->F->C->G

후위 순회(Postorder Traversal)

1. 왼쪽 서브트리를 후위 순회
2. 오른쪽 서브트리를 후위 순회
3. 루트노드 방문
   위 트리의 후위 순회 결과는 D->E->B->F->G->C->A

Binary Tree

각 노드가 자식 노드를 최대 2개까지 가지는 트리이다.
각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지 지정된다.

완전 이진 트리(complete binary tree)

왼쪽 자식 노드부터 순서대로 노드가 채워지며 마지막 레벨을 제외하고는
모든 자식 노드가 채워져있는 트리를 말한다.
마지막 레벨 역시 노드가 왼쪽에서 부터 순서로 채워져야 한다.

포화 이진 트리(perfect binary tree)

모든 노드가 0개 혹은 2개의 자식 노드를 가지며 모든 리프노드가 똑같은 레벨에 있는 경우의 트리를 말한다.

정 이진 트리(full binary tree)

정 이진 트리(full binary tree)는 모든 노드가 0개 혹은 2개의 자식 노드를 가지는 트리를 말한다.

편향 이진 트리(skewed binary tree)

말 그대로 노드들이 전부 한 방향으로 편향된 트리를 말한다.

binary search tree

이진 탐색 트리(binary search tree)는 이진 트리의 한 종류이다.
이진 트리이지만 왼쪽 자식 노드가 루트 노드보다 값이 작고,
오른쪽 자식 노드가 루트 노드보다 값이 큰 트리를 말한다.