Tree(python)

09 Dec 2020 in Data Structure on 자료구조, 트리, Python

트리

정점(node)와 간선(edge)로 구성

용어

• 루트(root) 노드 :맨 위의 노드
• 리프(leaf) 노드 : 간선이 없는 노드
• 내부(internal) 노드 : 루트도 리프도 아닌 노드
• sibling 노드 : 같은 부모의 child 노드들간의 관계
• 조상(ancestor) : 부모의 부모(의 부모의 …)
• 후손(descendant) : 자식의 자식(의 자식의 …)
• 노드의 수준(level) : 루트 노드로부터 해당 노드까지 거치게 되는 간선의 개수
• 트리의 높이(height or depth) = 최대 수준(level) + 1
• 서브 트리 :
• 노드의 차수 : 서브 트리의 개수
• 이진 트리(binary tree) : 모든 노드의 차수가 2이하인 트리(서브 트리의 개수가 2개 이하)
• 포화 이진 트리(full binary tree) : 모든 level에서 노드들이 모두 채워져 있는 이진 트리
  (leaf 노드들을 제외한 노드들은 모두 서브 트리 개수가 2개)
  (높이가 k 이고 노드의 개수가 2^k - 1 인 이진 트리)

• 완전 이진 트리(complete binary tree) : 레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리 (k는 높이) 레벨 k-1 에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리