p.246 ~ p.266
트리
리스트, 스택, 큐와 같은 자료구조들 -> 선형 자료구조 트리 -> 계층적인 구조 ex) 결정 트리 -> 인간의 의사 결정 (인공지능 문제에서 많이 사용)
트리에서 한 개 이상의 노드로 이루어진 유한 집합이다.
이들 중 하나의 노드는 루트 노드라 불리우고 나머지 노드들은 서브 트리라고 불리운다
트리에서 루트와 서브트리는 선으로 연결된다. 이 연결선을 간선(edge)라고 한다.
노드들 간에는 부모 관계, 형제 관계, 조상과 자손 관계가 존재한다.
조상노드 : 루트 노드에서 임의의 노드까지의 경로를 이루고 있는 노드들
자손노드 : 임의의 노드 하위에 연결된 모든 노드
단말노드(terminal) : 자식 노드가 없는 노드
비단말노드(nonterminal) : 자식 노드가 있는 노드
노드의 차수(degree) : 어떤 노드가 가지고 있는 자식 노드의 개수를 의미
트리의 차수 : 트리가 가지고 있는 노드의 차수 중에서 가장 큰 차수
레벨은 트리의 각 층에 번호를 매기는 것으로 정의에 의하여 루트의 레벨은 0이 되고 한 층씩 내려갈수록 1씩 증가한다.
트리의 높이는 트리가 가지고 있는 최대 레벨을 뜻한다.
나무가 모여서 숲이 되듯이 트리들의 집합을 포레스트라고 한다.
트리의 종류
가장 일반적인 방법은 각 노드가 데이터를 저장하는 데이터 필드와 자식 노드를 가리키는 링크필드를 가지게 하는 것 자식 노드의 개수만큼 링크를 만들어서 하면 된다. 하지만 이렇게 되면 노드의 크기가 고정되지 않아서 프로그램이 복잡하게 된다.
이진 트리
트리 중에서 가장 많이 쓰인다. 모든 노드가 2개의 서브트리를 가지고 있는 트리를 이진트리(binary tree)라고 한다. 서브 트리는 공집합일 수 있다. 따라서 이진 트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수가 2 이하가 된다. 공집합도 이진 트리라는 점에 주의하라. 또한 이진 트리에는 서브 트리 간의 순서가 존재한다. 따라서 왼쪽 서브트리와 오른쪽 서브 트리는 서로 구별된다.
이진 트리 정의
(1) 공집합이거나
(2) 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서브 트리들은 모두 이진트리여야 한다.
이진 트리가 순환적으로 정의되고 있음에 유의하자. (이진트리의 서브트리도 이진 트리의 성질을 만족하여야 한다.)
이진트리와 일반 트리의 차이점
- 이진 트리의 모든 노드는 차수가 2 이하, 일반 트리는 자식 노드의 개수에 제한이 없다
- 일반 트리와는 달리 이진 트리는 노드를 하나도 갖지 않을 수도 있다.
- 서브 트리간에 순서가 존재한다는 점도 다른 점이다. 따라서 왼쪽 서브 트리와 오른쪽 서브트리를 구별한다.
이진트리의 성질
- n개의 노드를 가진 이진 트리는 정확하게 n-1개의 간선을 가진다. 왜냐하면 이진 트리에서의 노드는 루트를 제외하면 정확하게 하나의 부모 노드를 가진다. 그리고 부모와 자식간에는 정확하게 하나의 간선만이 존재한다. 따라서 간선의 개수는 n-1개이다.
- 높이가 h인 이진 트리의 경우 최소 h개의 노드를 가지며 최대 2의h승-1개의 노드를 가진다.
이진 트리의 분류
- 포화 이진 트리 : 트리의 각 레벨에 노드가 꽉 차있는 이진 트리 * 노드에 번호를 부여하는 방법은 레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙이면 된다.
- 완전 이진 트리 : 마지막 레벨을 제외하고 모든 레벨이 완전하게 채워져 있고 마지막 레벨에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져있는 이진트리이다. 마지막 레벨에서는 노드가 꽉차있지 않아도 되지만 중간에 빈곳이 있어서는 안된다.
- 기타 이진 트리
이진 트리의 표현
- 배열을 이용하는 방법
- 포인터를 이용하는 방법
저장하고자 하는 이진 트리를 완전 이진트리라고 가정하고 이진 트리의 깊이가 K이면 최대 2K-1개의 공간을 연속적으로 할당한 다음, 완전 이진트리의 번호대로 노드들을 저장한다. ※ 인덱스 0을 사용하지 않는 편이 계산을 간단하게 만든다.
일반 이진트리는 배열을 사용하면 저장할 수는 있지만 기억공간의 낭비가 심해진다.
배혈 표현법에서는 인덱스만 알면 부모나 자식을 쉽게 알 수 있다.
- 노드 i의 부모 노드 인덱스 = i/2
- 노드 i의 왼쪽 자식 노드 인덱스 = 2i
- 노드 i의 오른쪽 자식 노드 인덱스 = 2i+1
링크 표현법에서는 트리에서이 노드가 구조체로 표현되고, 각 노드가 포인터를 가지고 있다. 이진트리를 링크표현법으로 표현하자면 왼쪽 자식노드, 데이터, 오른쪽 자식노드 이렇게 3개의 필드를 가진다.
typdef struct TreeNode{
int data;
struct TreeNode *left, *right;
}TreeNode;
7.4 이진 트리의 순회
이진 트리를 순회한다는 것은 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미한다. 트리는 여러가지 순서로 노드가 가지고 있는 자료에 접근할 수 있다.
이진 트리 순회 방법
- 전위
- 중위
- 후위
이는 루트와 왼쪽 서브 트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분된다. 만약 루트를 방문하는 작업을 V라고 하고 왼쪽 서브트리 방문을 L 오른쪽 서브트리 방문을 R이라고 하면 다음과 같이 세가지 방법을 생각할 수 있다.
- 전위 순회 : VLR
- 중위 순회 : LVR
- 후위 순외 : LRV
각각의 서브 트리들도 마찬가지로 전체 이진 트리와 똑같은 방법으로 적용될 수 있다.
전위 순회
① 루트 노드를 방문한다. ② 왼쪽 서브트리를 방문한다. ③ 오른쪽 서브트리를 방문한다.
알고리즘
- 노드 x가 NULL이면 더이상 순환 호출x
- x의 데이터를 출력한다.
- x의 왼쪽 서브 트리를 순환 호출하여 방문한다
- x의 오른쪽 서브 트리를 순환 호출하여 방문한다.
중위 순회
① 왼쪽 서브 트리를 방문한다. ② 루트 노드를 방문한다. ③ 오른쪽 서브 트리를 방문한다.
알고리즘
- 노드 x가 NULL이면 더 이상 순환 호출을 하지 않는다.
- x의 왼쪽 서브 트리를 순환 호출하여 방문
- x의 데이터를 출력한다
- x의 오른쪽 서브 트리를 순환 호출하여 방문
후위 순회
① 왼쪽 서브 트리를 모든 노드를 방문한다. ② 오른쪽 서브 트리의 모든 노드를 방문한다. ③ 루트 노드를 방문한다.
알고리즘
- 노드 x가 NULL이면 더 이상 순환 호출을 하지 않는다.
- x의 왼쪽 서브 트리를 순환 호출하여 방문
- x의 오른쪽 서브 트리를 순환 호출하여 방문한다.
- x의 데이터를 출력한다.
전위 순회: F, B, A, D, C, E, G, I, H (root, left, right) 중위 순회: A, B, C, D, E, F, G, H, I (left, root, right) 후위 순회: A, C, E, D, B, H, I, G, F (left, right, root) 레벨 순서 순회: F, B, G, A, D, I, C, E, H
자식노드를 처리한 다음에 부모노드를 처리 해야한다면 후외 순회를 부모노드를 처리한 다음에 자식노드를 처리해야 한다면 전위 순회를 사용하여야 한다.
레벨순회
레벨 순회는 각 노드를 레벨 순으로 검사하는 순회 방법이다.
이진 트리 연산 전까지.
참고자료
C언어로 쉽게 풀어쓴 자료 구조 천인국(저) 2005년