[자료구조] 트리(Tree)의 구조와 순회

🎁 트리(Tree)는 무엇인가요?

노드와 링크로 구성된 자료구조(그래프의 한 종류)이다.
계층적 구조를 나타낼 때 사용한다.(ex. 폴더(디렉터리) 구조 , 조직도)

[이미지 출처] : https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c

🎁 트리의 구조

1. 노드(Node) : 트리 구조의 자료 값을 담고 있는 단위

2. 에지(Edge) : 노드 간의 연결선 (= Link, branch)

3. 루트 노드(Root Node) : 부모가 없는 노드(가장 상단의 노드)

4. 잎새 노드(Leaf Node) : 자식이 없는 노드(단말노드)

5. 부모 노드(Parent) : 연결된 2개의 노드 중 상위의 노드

6. 자식 노드(Child) : 연결된 2개의 노드 중 하위의 노드

7. 형제 노드(Sibling) : 같은 부모를 가지는 노드

8. 레벨(Level) : 트리의 특정 깊이를 가지는 노드의 집합

9. 높이(Height) : 트리에서 가장 큰 값

10. 크기(Size) : 자신을 포함한 자식 노드의 갯수

11. 차수(Degree) : 각 노드가 지닌 가지의 수

🎁 트리의 특징

1. 하나의 노드에서 다른 노드로 이동하는 경로는 1개이다.

2. 노드가 n개인 트리의 Edge의 수는 n-1 개이다.

3. Acylic(Cycle이 존재하지 않는다)

4. 모든 노드는 서로 연결되어 있다.

5. 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리가 된다.

🎁 트리의 순회

모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산이다.

💡 전위 순회(preOrder)

• 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드

 

[이미지 출처] : https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%A6%AC-Tree

💡 중위 순회(preOrder)

• 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드

[이미지 출처] : https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%A6%AC-Tree

💡 후위 순회(preOrder)

• 왼쪽 노드 -> 오른쪽 노드-> 현재 노드 

[이미지 출처] : https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%A6%AC-Tree

💡 레벨 순회(LevelOrder)

• 위쪽 레벨 부터 왼쪽 노드 -> 오른쪽 노드