ref : http://www.kocw.net/home/search/kemView.do?kemId=1335653
트리
노드, 루트, 부모 자식 형제, 리프 중간, 조상 자손
서브, 차수, 레벨, 트리의 높이, 포레스트
트리에 관한 정리
n개의 노드를 갖는 트리의 모서리 수 n-1
트리에서 모서리 제거하면 연결그래프가 아님
녿 u에서 v로의 유일한 경로가 ㅈ존재
이진트리
완전, 포화, 편향
이진 트리 구현
레벨 k 최대 노드 수 => 2**k
높이가 m 최대 노드 수 2**m+1
최소 노드수 m+1
이진트리 구현
배열, 연결 리스트
이진트리 순회
전위, 중위, 후위
이진 탐색 트리
노드가 가지고 있는 데이터에 따라 노드의 위치를 탐색
트리의 활용
최소 신장 트리(prim, kruscal), 허프만 알고리즘
트리의 예시
꼭지점 모두.
- 절대적임.
- 같은 단게예 있고 부모가 같은 노드들
- 루트에서 한 노트로 가는 동안 있는 모든 노드
- 조상과는 반대로 리프 노드를 제외한 모든 노드가 자손노드를 가짐.
- 자손 descendant 노드 아니구 자식 child 노드다!!!
- 루트는 레벨 0!!!
레벨 예시
- 루트랑 가지 제거!
트리 예제
- 이진트리에서 노드가 왼쪽에 있는거랑 오른쪽에 잇는거 구분
이진트리의 서브트리:
완전이진트리 판별 :
포화이진트리 예시:
- 한쪽에만 치우침
이진트리 예제:
- 레벨 0은 루트노드라 노드수는 2의 0승 = 1
- 높이=깊이=최대 레벨
- 증명은 수학적 귀납으로 가능
연결리스트로 구현 예시:
preorder traversal 예시 :
중위순회 예시:
후위순회예시:
최소신장트리, 허프만코드
- node는 다 포함!!
그래프 G와 시장트리 예시
- 순환은 안되게 선택해라!
예시:
- 프림은 한개만 선택하지만 크루스칼은 여러개가 있으면 모두동시에 선택함.
예시
--> 모양은 다를 수 잇으나 비용 결과같은 프림과 같음
예시: