트리(Tree) 구조

트리 구조란?
노드로 이루어진 자료 구조

1. 트리는 하나의 루트 노드를 갖는다
2. 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
3. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

---

트리 특징

• 트리는 노드들과 노드들을 연결하는 간선으로 구성되어있다.
  : 노드가 N개인 트리는 항상 N-1개의 간선(edge)를 가진다.
• 트리는 비선형 자료구조로 계층적 관계를 표현
• 사이클이 없는 하나의 연결 그래프
• DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류이다.
• 트리는 이진 트리, 이진 탐색 트리, 균형트리, 이진힙 등이 있다.

---

트리 순회

트리의 모든 노드들을 방문하는 과정
전위 순회, 중위 순회, 후위 순회

📌 선형 자료구조 (연결리스트, 스택, 큐 등)는 순차적으로 요소에 접근하지만 트리 자료구조는 다른 방식을 사용해야함

전위 순회(Preorder)

: 깊이 우선 순회(DFT, Depth-First Traversal)이라고도 함

A -> B -> D -> E -> C -> F -> G

중위 순회(Inorder)

: 왼쪽, 오른쪽 대칭 순서로 순회를 하기 때문에 대칭순회라고도 함
: 이진 탐색트리(BST)에서 오름차순, 내림 차순으로 값을 가져올 때 사용됨.
(내림차순으로 값을 가져오기 위해서는 역순(오른쪽->root->왼쪽)으로 중위 순회를 하면 됩니다.)

D -> B -> E -> A -> F -> C -> G

후위 순회(Postorder)

: 트리를 삭제하는데 주로 사용됨.
(부모노드를 삭제하기 전에 자식 노드를 삭제하는 순으로 노드를 삭제해야하기 때문)

D -> E -> B -> F -> G -> C -> A

---

참고 블로그
참고 블로그
트리 종류