트리는 계층적인 구조를 표현할 때 사용할 수 있는 자료구조다.
정점(node)와 간선(edge)를 이용하여 데이터의 배치 형태를 추상화한다.
[트리의 용어]
- 루트노드(root node) : 부모가 없는 최상위 노드
- 단말노드(leaf node) : 자식이 없는 노드
- 크기(size) : 트리에 포함된 모든 노드의 개수
- 깊이(depth) : 루트 노드부터의 거리
- 높이(height) : 깊이 중 최댓값
- 차수(degree) : 각 노드의 (자식 방향) 간선 개수
기본적으로 트리의 크기가 N일때, 전체 간선의 개수는 N-1개 이다.
[이진 탐색 트리]
이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종이다.
왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 를 만족시킨다.
[트리의 순회]
트리 순회 방법은 3가지가 존재한다.
- 전위 순회(pre-order traverse) : 루트를 먼저 방문 (루트->왼->오)
- 중위 순회(in-order traverse) : 왼쪽 자식을 방문한 뒤에 루트를 방문 (왼->루트->오)
- 후위 순회(post-order traverse) : 왼쪽과 오른쪽 자식을 방문한 뒤에 루트를 방문 (왼->오->루트)
[트리 코드]
from logging import root
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
def init_tree():
global root
new_node = Node("A")
root = new_node
new_node = Node("B")
root.left = new_node
new_node = Node("C")
root.right = new_node
new_node_1 = Node("D")
new_node_2 = Node("E")
node = root.left
node.left = new_node_1
node.right = new_node_2
new_node_1 = Node("F")
new_node_2 = Node("G")
node = root.right
node.left = new_node_1
node.right = new_node_2
def preorder_traverse(node):
if node == None : return
print(node.data, end='->')
preorder_traverse(node.left)
preorder_traverse(node.right)
def inorder_traverse(node):
if node == None : return
inorder_traverse(node.left)
print(node.data, end='->')
inorder_traverse(node.right)
def postorder_traverse(node):
if node == None : return
postorder_traverse(node.left)
postorder_traverse(node.right)
print(node.data, end='->')
init_tree()
if __name__ == "__main__":
preorder_traverse(root)
print()
inorder_traverse(root)
print()
postorder_traverse(root)
트리 코드 출처 - https://lsjsj92.tistory.com/465
'Languages > Python' 카테고리의 다른 글
[Python] 이분 탐색 (0) | 2022.01.18 |
---|---|
[python] 투 포인터(Two Pointers) 알고리즘 (2) | 2022.01.14 |
정규표현식 re/compile/파이썬 (0) | 2021.08.04 |
힙 / 힙큐(heapq) (0) | 2021.08.03 |
파이썬 스택, 큐 (0) | 2021.07.22 |