[파이썬(Python)] 트리(Tree)

 

 

트리는 노드(node)와 노드를 잇는 가지(edge)로 구성된다.

• 루트(root): 트리에 단 하나만 존재하는 최상단에 위치한 노드
• 리프(leaf): 하단으로 뻗은 가지가 없는 노드
• 비단말 노드(non-terminal node): 리프를 제외한 모든 노드. 내부 노드
• 부모: 연결된 두 노드 중 상단에 위치한 노드
• 자식: 연결된 두 노드 중 하단에 위치한 노드
• 형제: 부모가 같은 노드
• 조상: 특정 노드에서 위쪽으로 가지를 따라가며 만나는 모든 노드
• 자손: 특정 노드에서 아래쪽으로 가지를 따라가며 만나는 모든 노드
• 레벨: 루트에서 얼마나 멀리 떨어져 있는지를 나타내는 정도. 루트의 레벨은 0
• 차수: 각 노드가 갖는 자식의 수 - (이진트리: 차수 2, 삼진트리: 차수 3)
• 서브트리: 특정 노드를 루트로 삼아 해당 노드와 자손으로 구성된 트리
• 빈 트리: 노드와 가지가 전혀 없는 빈 트리. 널 트리

 

 

순서 트리 & 무순서 트리

형제 노드간 순서 관계가 있으면 순서 트리, 그렇지 않으면 무순서트리이다.

 

 

순서 트리의 검색

너비 우선 검색(breadth-first search)

낮은 레벨(상단)부터 왼쪽에서 오른쪽으로 검색한다. 한 레벨의 검색을 마치면 다음 레벨의 왼쪽으로 돌아가 다시 검색을 시작한다. 폭 우선 검색, 가로 검색, 수평 검색이라고도 한다.

 

깊이 우선 검색(depth-first search)

리프에 도달할 때까지 하향 검색한다. 리프에 도달하면 한 레벨 올라가서, 다시 내려갈 노드가 있으면 내려가서 검색한다. 스캔 순서에 따라 전위 순회, 중위 순회, 후위 순회로 구분된다. 단순히 노드를 지나가는 것과 스캔(방문)하는 것을 혼동하지 않도록 주의한다.

 

 

---

 

 

Reference

Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편