📚 Tree
계층적인 구조를 표현할 때 사용하는 자료구조
트리 관련 용어
| 명칭 | 의미 |
|---|---|
| 루트 노드 (root node) | 부모가 없는 최상위 노드 |
| 단말 노드 (leaf node) | 자식이 없는 노드 |
| 크기 (size) | 트리에 포함된 모든 노드의 개수 |
| 깊이 (depth) | 루트 노드부터의 거리 |
| 높이 (height) | 깊이 중 최댓값 |
| 차수 (degree) | 각 노드의 (자식 방향) 간선 개수 |
📚 트리의 순회
- 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법
전위 순회 (Pre-order traverse)
1
2
3
4
def preorderTraversal(node):
print(node)
if node.left: preorderTraversal(node.left)
if node.right: preorederTraversal(node.right)
중위 순회 (In-order traverse)
1
2
3
4
def inorderTraversal(node):
if node.left: inorderTraversal(node.left)
print(node)
if node.right: inorderTraversal(node.right)
후위 순회 (Post-order traverse)
1
2
3
4
def postorderTraversal(node):
if node.left: postorderTraversal(node.left)
if node.right: postorderTraversal(node.right)
print(node)