2019.07.13 Tree
(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)
# 질문에 답하기
트리
- 어떤 노드 간에 경로가 존재해야 한다.( 즉 연결이 되어 있어야 한다) - connected
- 단 사이클이 없어야 한다 - acyclic
- set안에 tree와 tree가 있으면 forest이다
- 루트 노드가 없어지면 각각 분리집합으로 분할 가능
트리 용어
- 레벨와 트리의 높이가 같다고 하면 한쪽으로 굉장히 치우진 것과 같다.
엣지와 노드와의 관계
- MST : KRUSKAL 알고리즘 -> 도시계획
- CS/binary_tree.pdf at master · ythwork/CS
이진트리
이진트리의 특징
완전 이진 트리
추가 공부할 사항
- 포화 이진 트리
- 편향 이진 트리
이진트리의 순회
- 스텍기반
- 전회순회
- 중위순회
- 후위순회
- 큐 기반
- 레벨 순회
전위순회(pre order)
class TreeNode:
def __init__(self, data):
self.data=data
self.left=None
self.right=None
def preorder(node):
#base case
if not node:
return
#노드를 방문했다고 치고 print로 찍어봄 실제로는 오퍼레이션을 넣고 방문할 떄 마다 실행
print(node.data, end = " ")
# 왼쪽 자식
preorder(node.left)
# 오른쪽 자식
preorder(node.right)
if __name__ == "__main__":
n1 = TreeNode(1)
n2 = TreeNode(2)
n3 = TreeNode(3)
n4 = TreeNode(4)
n5 = TreeNode(5)
n6 = TreeNode(6)
n7 = TreeNode(7)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7
preorder(n1)
중위순회(in order)
def preorder(node):
#base case
if not node:
return
# 왼쪽 자식
preorder(node.left)
#노드를 방문했다고 치고 print로 찍어봄 실제로는 오퍼레이션을 넣고 방문할 떄 마다 실행
print(node.data, end = " ")
# 오른쪽 자식
preorder(node.right)
후위순회 (post order)
def preorder(node):
#base case
if not node:
return
# 왼쪽 자식
preorder(node.left)
# 오른쪽 자식
preorder(node.right)
#노드를 방문했다고 치고 print로 찍어봄 실제로는 오퍼레이션을 넣고 방문할 떄 마다 실행
print(node.data, end = " ")