자료구조 - Tree (1)

 

 

Tree 란?

 

 

• 비선형 자료구조인 Tree는 계층적인 관계 구조를 지닌다.

 

• 여러개의 노드로 이루어지며 이들이 연결된 형태로 데이터를 구성함.

 

 

 

Tree의 구성 요소

 

 

• 구성 요소로는 루트(root) 노드, 자식(child) 노드, 부모(parent) 노드, 리프(Leaf) 노드 등이 있으며 노드의 위치와 거리는 깊이(Depth) 와 높이 (Height) 로 나타낸다.

 

---

 

○  노드 (Node)

 

• 트리의 구성 요소 (Data)

 

• 모든 트리는 여러개의 노드를 바탕으로 이루어짐.

 

 

 

○  간선 (Edge)

 

• 노드와 노드를 연결하는 선이다.

 

• 전체적인 트리의 구조를 형성하는 역할

 

 

 

○  루트 노드 (Root Node)

 

• 트리 구조의 최상단에 위치하는 노드

 

• 트리의 시작점이고 루트 노드는 부모가 없음

 

 

 

○  리프 노드 (Leaf Node)

 

• 자식이 없는 노드이며 트리의 최하단에 위치함.

 

 

○  부모 노드 (Parent Node)

 

• 특정 노드의 상위에 위치하는 노드

 

• 자식 노드들과 연결됨

 

 

 

○  자식 노드 (Child Node)

 

• 노드가 가지는 특징으로 노드는 한개 이상의 자식 노드를 가질 수 있음.

 

• 보통의 트리에서 자식 노드는 하나의 부모 노드에 연결될 수 있음.

 

 

 

○  형제 노드 (Sibling Node)

 

• 같은 부모를 공유하는 노드임

 

• 트리 내에서 같은 깊이(Depth)에 위치함.

 

 

---

 

 

그 외의 트리 표현 요소

 

 

○  서브 트리 (SubTree)

 

• 트리의 한 노드로 부터 해당 노드의 자식 노드들로 구성된 부분트리를 의미함.

 

 

• 위 그림에서 4번 노드의 서브트리는 7번 노드와 8번 노드이며 1번 노드의 Subtree는 4,5,7,8번 노드임,

 

• 즉 하나의 나뭇가지처럼 이루어지는 구성요소를 의미함.

 

 

 

 

○  깊이 (Depth)

 

• 루트 노드로 부터 특정 노드까지의 거리. (루트 노드의 깊이는 0 임)

 

 

○  높이 (Height)

 

• 특정 노드 에서 리프 노드까지의 거리 (리프 노드의 높이는 0 임)

 

 

 

 

 

 

 

 

 

 

 

 

 

사진 출처 : https://www.geeksforgeeks.org/tree-data-structure/

Tree Data Structure - GeeksforGeeks

https://www.geeksforgeeks.org/sub-tree-nodes-tree-using-dfs/?ref=header_search

Subtree of all nodes in a tree using DFS - GeeksforGeeks