16. 이진트리(8-2)

1. 이진트리(binary tree)의 개념 

 이진 트리의 정의 

 공 트리(empty tree)이거나 근 노드와 왼쪽 서브트리(left subtree)와 

    오른쪽 서브트리(right subtree)라 부르는 2개의 분리된 노드의 유한  

    집합으로 모든 노드가 2개 이하의 가지를 가진  

즉, 각 노드의 차수가  모두 2 이하인 트리 

 정 이진 트리(full binary tree 또는 포화 이진 트리) 

 깊이가 k인 트리에서 최대 노드의 개수 n=2k-1이고, 레벨이 l 인  

    노드의 수가 2l-1 인 트리 

 이 때, k 레벨의 노드들만 차수가 0(zero)이고, 나머지 노드는 모두 

    차수가 2가 된다. 

 정이진 트리의 예 

 완전 이진 트리(complete binary tree) 

 깊이가 k이고 전체 노드의 개수가 n일 때, 1부터 n까지의 노드들이 

    위에서 아래로, 왼쪽에서 오른쪽으로 순차적인 대응이 되는 트리 

 레벨이 l 에서 노드의 개수가 2l-1-1 < n < 2l

-1이인 트리 

 정이진 트리를 구성하기 위한 트리의 연결 순서 

 엄밀한 이진 트리 

 각 노드의 차수가 0 이거나 2인 이진 트리 

 엄밀한 이진 트리에서 단말 노드의 개수를 구하는 식 

 n0 = n2 + 1 

 여기서 n0은 단말 노드의 개수이고 n2는 차수가 2인 노드의 개수이다. 

  Knuth 이진 트리와 엄밀한 이진트리 

 Knuth 이진 트리 

 각 노드의 차수가 0, 1또는 2인 트리 

 

 사향 이진 트리(skewed binary tree, 경사 이진 트리) 

 트리의 노드들이 왼쪽, 오른쪽의 한쪽 방향으로만 치우친 이진 트리 

 일반 트리와 이진 트리의 차이점 

 일반 트리는 공백 트리(empty tree)가 없지만, 이진 트리는 공 트리가 있다. 

 일반 트리는 자식 노드의 위기가 특별한 의미가 없지만, 이진 트리는 왼쪽 자식노드와 오른쪽 자식 

노드가 분명히 구별된다. 즉, 이진 트리에서는 좌사향 이진 트리와 우 사향 이진 트리가 서로 다른 

이진 트리가 된다. 

 일반 트리는 차수가 2이상 나올 수 있지만, 이진 트리는 반드시 2이하로 구성된다. 

 

 이진 트리의 성질 

 이진 트리에서 깊이가 k일 때  최대 노드수 n과 관계 

 n  ≤ 2k – 1 

 여기서 , n은 최대 노드의 개수이고 k는 깊이를 말한다. 이 때 K ≥ 1 이다. 

 이진 트리에서 단 노드 n0와 차수가 2인 중간 노드 n2와의 관계 

 N0 = n2 + 1