2.5.2 이진트리

2.5.2 이진트리
이진트리(binary tree) - 모든 노드의 차수가 최대 2를 넘지 않는 트리.

이진트리의 모든 노드 - 최대 2개의 서브트리(왼쪽 서브트리와 오른쪽 서브트리 - 왼쪽 노드와 오른쪽 노드에 ‘순서’ 부여)

이진트리의 특성 - N개의 노드를 가진 이진트리의 최대 높이와 최소 높이를 계산 가능.
이진트리의 최대 높이는 N개의 노드를 사용해서 왼쪽 또는 오른쪽으로 치우친 이진트리(경사 이진트리)를 형성하는 경우. - 노드의 개수와 같은 N

이진트리의 최소 높이 - 각 노드가 최대 2개의 자식 노드를 채워서 갖는 경우 - [logN] +1이 최소 높이

이진트리에 대한 주요 연산 - 삽입, 삭제, 순회
순회(traverse) - 이진트리의 순회 연산은 일정한 순서에 따라 트리에 있는 각 노드를 한 번씩 방문하는 것. (이 순회 연산으로 트리 내의 저장된 정보를 선형적인 순서의 정보로 만듦)

데이터를 나타내는 루트 노드(D), 왼쪽 서브트리(L), 그리고 오른쪽 서브트리(R)로 간단히 구성되어 있다고 가정하면, 모두 여섯 가지의 서로 다른 방문 순서, LDR, RDL, LRD, RLD, DLR, DRL을 얻음.

항상 왼쪽 서브트리를 먼저 방문한다고 가정하면 세 가지 형태로 줄일 수 있다.
•DLR: 루트 노드 방문 → 왼쪽 서브트리 방문 → 오른쪽 서브트리 방문
•LDR: 왼쪽 서브트리 방문 → 루트 노드 방문 → 오른쪽 서브트리 방문
•LRD: 왼쪽 서브트리 방문 → 오른쪽 서브트리 방문 → 루트 노드 방문

루트 노드를 어느 시점에 방문하느냐에 따라 결정.

왼쪽 서브트리와 오른쪽 서브트리를 방문하기 전에 루트 노드를 방문하면 전위(preorder) 순회, 왼쪽 서브트리와 오른쪽 서브트리 사이에 루트 노드를 방문하면 중위(inorder) 순회, 그리고 왼쪽 서브트리와 오른쪽 서브트리를 모두 방문한 다음에 루트 노드를 방문하면 후위(postorder) 순회.

2.5.3 특수한 조건을 갖는 이진트리

포화 이진트리 - 각 레벨에서 빈 자리가 없이 노드를 갖음, 모든 내부 노드들은 2개의 자식 노드를 갖음.

포화 이진트리(full binary tree)란 깊이가 k인 이진트리 중에서 노드의 개수가 2^k -1 개인 이진트리이다. 즉, 깊이가 k인 이진트리가 가질 수 있는 노드의 최대 개수는 2^k -1이며, 단말 노드의 개수가 2^k-1개다.
예] [그림2-22] 깊이 4인 이진트리, 마지막 레벨 3까지 빈 자리 없이 총 2^4 -1=15개의 노드로 채워진 포화 이진트리.

완전 이진트리(complete binary tree) -  트리의 최대 레벨이 k일 때, 레벨 k-1까지는 포화 이진트리를 형성. 레벨 k에서는 왼쪽부터 오른쪽으로 채워진 트리
-> 완전 이진트리 - 총 노드의 개수가 2^k+1 -1을 초과하지 않으면서 연속적인 번호를 갖는 트리.
* 포화 이진트리는 완전 이진트리에 포함되지만, 완전 이진트리는 포화 이진트리가 아니다.

경사 이진트리(skewed binary tree) -  한쪽 방향으로만 가지가 뻗어 나간 이진트리. (왼쪽 방향으로만 가지가 뻗어 나간 경사 이진트리와 오른쪽으로만 가지가 뻗어 나간 경사 이진트리)