-
[자료구조] 트리개발/자료구조와 알고리즘 2022. 1. 26. 02:03
트리
단순 선형 자료구조에서는 계층을 나타내기가 어렵다.
따라서 계층적 자료구조를 만들기 위해서 트리를 생각했다.
값을 가지는 노드와, 노드 사이를 잇는 간선으로 이루어져 있으며,
부모 - 자식 관계를 가진다.
트리를 그림으로 나타내면 위와 같다.
여기서 A - B, C, D의 관계를 부모 - 자식 관계라 하며,
마찬가지로 B - E, F의 관계도 부모 - 자식 관계이다.
가장 위에 있는 노드인 A를 루트(Root)노드라 하고,
자식이 없는 노드들(E, F, C, G)를 리프(Leaf)노드라 한다.
위의 트리는 3개의 층으로 되어있는데, 이를 높이가 3인 트리라고 한다.
트리는 서브트리로 나눌 수 있다.
이렇게 나누면 B와 D는 각각의 서브트리에서 루트노드가 된다.
트리의 자식이 연결되어 싸이클이 생기면 그래프가 된다.
이진트리(Binary Tree)
부모의 자식이 최대 둘인 트리를 이진 트리라 한다.
자료 순회
앞에서부터 쭉 탐색하는 선형구조와 달리 트리는 계층적 구조이므로 여러가지 방식으로 자료를 순회할 수 있다.
- preorder - ABDECF
- inorder - DBEACF
- postorder - DEBFCA
- levelorder - ABCDEF
간단한 이진트리와 순회코드들은 다음과 같다.
from collections import deque class Node: def __init__(self, item): self.left = None self.right = None self.data = item class BinaryTree: def __init__(self): self.root = None def preorder(self, n): if n: print(n.data, end='') self.preorder(n.left) self.preorder(n.right) def postorder(self, n): if n: self.postorder(n.left) self.postorder(n.right) print(n.data, end='') def inorder(self, n): if n: self.inorder(n.left) print(n.data, end='') self.inorder(n.right) def levelorder(self,n): q = deque([n]) while q: cur = q.popleft() if cur is not None: print(cur.data, end='') q.append(cur.left) q.append(cur.right) if __name__ == "__main__": BT = BinaryTree() BT.root = Node('A') BT.root.left = Node('B') BT.root.right = Node('C') BT.root.left.left = Node('D') BT.root.left.right = Node('E') BT.root.right.right = Node('F') print('preorder') BT.preorder(BT.root) print('\ninorder') BT.inorder(BT.root) print('\npostorder') BT.postorder(BT.root) print('\nlevelorder') BT.levelorder(BT.root)
위 처럼 코드를 구성하면 BT.root.left.right.~~~ 계속 늘어지게 된다.
삽입 삭제 연산은 다음 글에서 다뤄보자!
'개발 > 자료구조와 알고리즘' 카테고리의 다른 글
[자료구조] 그래프 (0) 2022.02.16 [자료구조] 힙(Heap) (0) 2022.02.05 [자료구조] 이진 탐색 트리(Binary Search Tree) (0) 2022.01.31 [자료구조] LinkedList (0) 2022.01.24 [자료구조] Queue & Stack (0) 2022.01.21