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

도입 지금까지 배운 자료구조는? 데이터가 계층적 구조를 가지면?

트리 트리(tree)란? 응용 분야 계층적 구조를 나타내는 자료구조 부모-자식 관계의 노드들로 구성 계층적인 조직 표현 파일 시스템 인공지능의 결정트리 등

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

트리 용어 루트(root): 부모가 없는 노드 서브 트리(subtree): 간선(edge):노드간의 연결 선 노드의 차수(degree): 서브 트리의 개수 단말 노드 또는 잎노드(terminal/leaf): 차수가 0인 노드 비 단말노드(non terminal): 단말 노드 이외의 노드들 자식 노드(child node): 노드 X의 서브 트리의 루트들은 X의 자식 부모 노드(parent node): X는 그 자식들의 부모 형제 노드(sibling node): 부모가 같은 자식들 조상 노드(ancestor node): 루트부터 노드에 이르는 경로상의 모든 노드들 자손 노드(descendent node): 서브 트리상의 모든 노드들 트리의 차수(degree): 트리에 속한 노드의 최대 차수 수준(level): 트리의 각 층에 매겨지는 번호, 루트의 레벨은 1, 한 층씩 내려갈수록 1씩 증가 높이(height) / 깊이(depth): 트리에 속한 노드의 최대 수준 포리스트(forest): 트리들의 집합 A B C D E F G H I J

예제: 트리 용어 B D E F C I H G 루트: 서브 트리: 간선: A 노드의 차수: 단말 노드 또는 잎노드: 비 단말노드: 자식 노드: 부모 노드: 형제 관계: 조상 노드: 자손 노드: 트리의 차수: 수준: 높이: B A D E F C I H G

트리 표현 트리 T를 리스트로 표현 서브 트리는 순환적으로 리스트로 표현 A B D E F C I H G B C D E F G 노드의 차수에 따라 링크 수가 달라지고, 효율적 알고리즘 작성을 위해서 노드 구조가 일정하는 것이 좋다. 트리의 차수가 2이면?

이진 트리 이진 트리(binary tree)의 정의 이진 트리와 일반 트리간의 차이점 공집합이거나 루트와 왼쪽 서브트리와 오른쪽 서브트리로 구성되며, 각 서브트리는 이진트리이다. (순환적 정의에 유의) 이진 트리와 일반 트리간의 차이점 자식 노드 개수의 제한성 공백 유무 서브트리간에 순서 존재 여부

이진 트리 다음 2개의 트리, T1, T2는 동일한가? 이진 트리 일반 트리 T1 T2 E E H H

예제: 이진 트리 이진 트리 예 루트 노드? 잎 노드? 중간 노드? 차수가 1인 노드는? 트리 높이? 트리 차수? B C D A C D E F G H I

편향 이진트리 왼편 또는 오른편으로 편향되어 있는 트리 (skewed binary tree)

이진트리의 성질 n개 노드를 가진 이진 트리가 갖는 간선의 개수는? B A C D E F G H I

이진 트리의 성질 높이가 h인 이진 트리는 최소 몇 개의 노드를 갖는가? 최대 몇 개의 노드를 갖는가? B C D E F G A C D E F G H I

이진 트리의 성질 N개의 노드를 갖는 이진 트리의 높이는? 최대 높이는? 최소 높이는? B A C D E F G H I

이진 트리의 종류 포화 이진트리(full binary tree) 완전 이진트리(complete binary tree) 각 트리 수준에 노드가 꽉 차 있는 이진트리 트리 수준 단위로 왼쪽부터 오른쪽의 순서로 번호 부여 완전 이진트리(complete binary tree) 트리 높이가 k일 때, 수준 1부터 k-1까지 노드가 모두 채워지고, 마지막 수준 k에서, 왼쪽부터 오른쪽의 순서로 노드가 채워지는 이진트리

이진 트리 표현 배열 표현 부모와 자식노드 인덱스간의 관계: 노드 i에 대해서 이진트리를 포화 이진트리로 가정하고, 각 노드에 번호를 부여하고(왼쪽부터), 그 번호를 배열의 인덱스로 사용 포화 이진트리나 완전 이진트리 표현에 적합 부모와 자식노드 인덱스간의 관계: 노드 i에 대해서 부모 노드 인덱스는? 왼쪽 자식 노드 인덱스는? 오른쪽 자식 노드 인덱스는? 트리의 높이가 k이면 적절한 배열의 크기는?

이진 트리 표현 링크 표현 링크를 이용하여 부모 노드가 자식 노드를 가리키게 하는 방법 노드는 다음 구조체로 표현: left data right 왼쪽 자식을 가리키는 링크 오른쪽 자식을 가리키는 링크 typedef struct treeNode { element data; struct treeNode *left, *right; }

이진 트리 순회 이진 트리 순회(traversal)란? 이진 트리 순회 방법 트리에 포함된 모든 노드를 방문하는 것 루트, 왼쪽 서브트리, 오른쪽 서브트리 중에서 루트를 언제 방문하는가에 따라서 구분 전위(preorder): 중위(inorder): 후위(postorder):

이진 트리 순회 전위 순회(preorder traversal) 순회 방법을 순환적으로 기술 다음 트리를 전위 순회하면? B C 루트 노드 방문 왼쪽 서브트리 방문 오른쪽 서브트리 방문 다음 트리를 전위 순회하면? B A C D E F G H I

이진 트리 순회 전위 순회 알고리즘 preorder(T) { } B A C D E F G H I

이진 트리 순회 중위 순회(inorder traversal) 순회 방법을 순환적으로 기술 다음 트리를 중위 순회하면? B C 왼쪽 서브트리 방문 루트 노드 방문 오른쪽 서브트리 방문 다음 트리를 중위 순회하면? B A C D E F G H I

이진 트리 순회 중위 순회 알고리즘 inorder(T) { } B A C D E F G H I

이진 트리 순회 후위 순회(postorder traversal) 순회 방법을 순환적으로 기술 다음 트리를 후위 순회하면? B 왼쪽 서브트리 방문 오른쪽 서브트리 방문 루트 노드 방문 다음 트리를 후위 순회하면? B A C D E F G H I

이진 트리 순회 후위 순회 알고리즘 postorder(T) { } B A C D E F G H I

트리 수준별 순회 트리의 수준별 순회(level order)란? 트리의 낮은 수준부터 높은 수준의 순서로 방문하되, 같은 수준에 있는 노드들을 좌측에서 우측의 순서로 모두 방문하는 순회 다음 트리를 수준별로 순회하면? B A C D E F G H I

트리 수준별 순회 트리 수준별 순회 알고리즘은? levelorder(T) { } 2 1 9 3 7 4 5 8 6 T 10 11 12 T

이진 트리 응용 수식 트리란(expression tree)? 수식 트리의 예 산술식, 논리식의 연산자와 피연산자로 트리를 구성 피연산자는 잎노드에, 연산자는 비단말노드에 위치 왼쪽 서브트리는 왼쪽 피연산자를, 오른쪽 서브트리는 오른쪽 피연산자를 표현 수식 트리의 예

수식 트리 다음 수식 트리를 평가하라.

수식 트리 수식 트리의 평가 알고리듬 수식 트리는 이항 연산자만 포함한다고 가정 eval(T) { // T가 null, 잎노드, 비단말노드로 구분 }

수식 트리 주어진 수식으로부터 수식 트리를 어떻게 구성할 것인가? 예제: 수식을 후위 식으로 변환 후위 식으로부터 수식 트리 구성 예제: 주어진 수식: 2 + 3 * 4

수식 트리 cons(exp) // exp의 후위 식으로부터 수식 트리를 구성하여 반환 { stack[n]; top <- -1; // 스택 생성 및 초기화 while (exp의 끝에 도달하지 않았으면) token <- getToken(exp); case { token = operand: // 잎노드를 구성하여 스택에 저장 token = operator: // 연산자 노드를 구성하고, // 스택으로부터 2개 노드를 꺼내어 서브트리로 설정하고, // 연산자 노드와 2개 서브트리로 구성된 트리를 구성하고, // 구성된 트리를 스택에 저장 } return pop(stack)); // 결과의 수식트리 반환