[자료구조] 트리(Tree)

 

트리(Tree)

---

안녕하세요? 장장스입니다.

오늘은 Tree 자료구조에 대해 알아보겠습니다.

 

 

트리 (Tree)

---

가계도처럼 노드를 나무 형태로 연결한 구조를 트리라고 합니다. 트리에 있는 각각의 요소는 노드입니다. 위 사진에서처럼 노드는 부모, 자식 형태로 이어집니다.

 

• 뿌리 (root): 트리의 시작 부분입니다. 뿌리를 통해 들어가서 트리를 탐색합니다.
• 잎 (leaf): 자식이 딸려있지 않은 부분입니다. 노드라고 부르기도 합니다.
• 간선 (edge): 두 노드를 연결하는 선입니다. 뿌리로부터의 간선의 수에 따라 level을 나눕니다.

 

 

트리의 높이, 깊이, 레벨

---

트리 자료구조에 대해 이야기하다 보면 높이, 깊이, 레벨에 대해 언급이 됩니다. 차이점에 대해 알아봅시다

 

 

• 높이(height): 루트에서 가장 먼 잎(노드) 까지 거치게되는 간선 개수를 말한다.
• 깊이(depth): 루트에서 현재 노드 사이의 간선 개수를 말한다.
• 레벨(level): 트리의 깊이와 정의가 비슷하지만 그 기준이 간선이 아닌 노드의 개수이다. 따라서 depth+1=leveldepth+1=level 이 성립한다.

 

 

 

 

 

 

 

 

Post

---

•  

References

---

• [부스트코스] 자바로 구현하고 배우는 자료구조

 

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)