자료구조: CHAP 7(2) 트리 2017. 5. 30 순천향대학교 컴퓨터공학과 하 상 호.

Presentation on theme: "자료구조: CHAP 7(2) 트리 2017. 5. 30 순천향대학교 컴퓨터공학과 하 상 호."— Presentation transcript:

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

2 목차 트리, 이진 트리의 개념 이진 트리의 성질 이진 트리 표현 이진 트리 순회 이진트리 응용: 수식 트리 트리 연산
스레드 이진트리 이진탐색트리

3 review T를 다음의 각 방법으로 순회하라. T를 배열로 표현하라. 전위 순서 중위 순서 후위 순서
preorder(T, 1)을 작성하라. 2 1 9 3 7 11 4 5 8 6 10 12 T

4 이진 트리 연산 (1) 트리에 포함된 노드의 개수는? 재귀적 정의를 주라 get_node_count(T) { }

5 이진 트리 연산 (2) 트리에 포함된 잎노드의 개수는? 재귀적 정의를 주라. get_leaf_count(T) { }

6 이진 트리 연산 (3) 트리의 높이는? 재귀적 정의를 주라. get_height(T) { }

7 스레드 이진 트리 트리 순회시 순환 호출은 비효율적 이진 트리의 null 링크를 이용하면 순환 호출 없이 트리 순회 가능
총 링크의 개수는? null 링크의 개수는?

8 스레드 이진 트리 Null 링크에 중위 순회시에 선행 노드인 중위 선행자(inorder predecessor)나 후속 노드인 중위 후속자(inorder successor)를 저장시켜 두면 비순환 호출 트리 순회 가능 이러한 트리를 스레드 이진트리(threaded binary tree)라 한다. right 링크가 중위 후속자를 가리킨다 스레드 이진트리가 올바른가?

9 스레드 이진 트리 스레드 이진트리 표현 링크가 자식을 가리키는지 스레드를 가리키는지를 구분하는 것이 필요
struct node{ int data; nodeptr left, right; int isThread; } 만약 오른쪽 링크가 스레드이면 true

10 스레드 이진 트리 다음 이진트리를 스레드 이진트리로 구성하라. B A C D E F G H I

11 스레드 이진 트리 중위 순회 알고리즘 B C D E F G H I A thread_inorder(T) p <-T;
while (p.left != null) do // 먼저 가장 왼쪽 노드로 이동 p <- p.left; repeat do visit(p); // p를 방문 p <- inorder_sucessor(p); // 중위 후속자 방문 while (p!= null); end thread_inorder inorder_successor(T) // T의 중위 후속자 반환 end inorder_successor