[이산수학 #11] 트리

트리 즉, 어떤 순환도 존재하지 않는 연결 그래프 트리의 성질 1. 순환 존재하지 않음 2. 유일한 루트 노드 3. 내차수가 0인 노드는 only 루트 노드, 나머지의 내차수는 1 트리의 용어 루트노드, 부모 자식노드, 터미널(리프 노드)는 제외 - 레벨 - 루트 노드의 레벨 = 0 - 어떤 노드의 레벨이 i일때, 자식의 레벨을 i+1 - 높이 - 정점들 중 최고의 레벨 (그래프 당 한 개) - 정점의 차수 - 특정 정점의 부분 트리 개수 (유향, 무향 다 가능) - 트리의 차수 - 모든 정점들의 차수 중 최대값 - n트리 - 모든 정점들의 자식이 최대 n개 - 리프 노드 외의 모든 정점들의 자식이 n개이면, 완전 n트리 - 예) 완전 이진트리 - 순서 트리 - 유향 그래프에서 같은 레벨에서 정점의 자식..