자료구조: CHAP 7 트리 –review 2016. 9. 1 순천향대학교 컴퓨터공학과 하 상 호.

Presentation on theme: "자료구조: CHAP 7 트리 –review 2016. 9. 1 순천향대학교 컴퓨터공학과 하 상 호."— Presentation transcript:

1 자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호

2 트리 형식적 정의 트리 예 한 개 이상의 노드들로 구성된 유한 집합 루트(root)라는 특정 노드 존재
나머지 노드들은 T1, T2, …, Tn으로 분할 T1, T2, …, Tn은 루트의 서브 트리라 한다. (재귀적 정의) 각 서브 트리는 disjoint 집합을 구성 트리 예 A B C D E F G H I J

3 트리 용어 루트: 간선(edge): 부모 노드 자식 노드 형제 관계(sibling) 단말 노드 또는 잎노드
비 단말노드 / 중간노드 조상 노드 자손 노드 노드의 차수(degree): 트리의 차수: 수준(level) 높이(height): 서브 트리(subtree): B A D E F C I H G A B C D E F G H I J

4 이진 트리 정의? 공집합이거나 루트와 왼쪽 서브트리와 오른쪽 서브트리로 구성되며, 각 서브트리는 이진트리이다. (순환적 정의에 유의) 이진 트리 예 루트 노드? 잎 노드? 중간 노드? 차수가 1인 노드는? 트리 높이? 트리 차수? B A C D E F G H I

5 이진 트리 이진 트리의 유형 이진 트리 표현 포화 이진트리(full binary tree)
완전 이진트리(complete binary tree) 편향 이진트리(skewed binary tree) 이진 트리 표현 배열 리스트 B A C D E F G H I

6 이진 트리 성질 이진 트리의 성질 n개 노드를 가진 이진 트리가 갖는 간선의 개수는?
높이가 h인 이진 트리는 최대/최소 몇 개의 노드를 갖는가? n개의 노드를 갖는 이진 트리의 최대/최소 높이는?

7 이진 트리 순회 이진 트리 순회란? 이진 트리 순회 알고리즘은? B A C D E F G H I

8 이진 트리 연산 이진 트리의 연산 트리에 포함된 노드의 개수를 구하는 알고리즘은?
트리에 포함된 잎노드의 개수를 구하는 알고리즘은? 트리의 높이를 구하는 알고리즘은? B A C D E F G H I

9 스레드 이진 트리 스레드 이진 트리 트리의 Null 링크에 중위 순회시에 선행 노드인 중위 선행자(inorder predecessor)나 후속 노드인 중위 후속자(inorder successor)를 저장시켜서 비순환적으로 트리 순회를 가능하게 하는 트리 스레드 이진트리 표현 중위 순회 알고리즘? B A C D E F G H I struct node{ int data; nodeptr left, right; int isThread; }

10 이진 탐색 트리 이진 탐색 트리 정의? 탐색 알고리즘은? 위 알고리즘의 복잡도는? 2 5 7 1 4 6 8 3 9

11 이진 탐색 트리 다음 순서로 자료가 입력되었다고 가정하여 이진 탐색트리를 구성하라.
5, 3, 7, 2, 4, 6, 9, 1, 8, 10 위에서 구성한 트리에 대해서 다음 노드를 순서대로 삭제하라. 1 7 5

12 이진 탐색 트리 이진 탐색 트리 삽입 알고리즘은? 삭제 알고리즘은? 2 5 7 1 4 6 8 3 9