자연계열 3번

(3-1)높이가 $\displaystyle h$인 이진트리의 최대 노드 개수= level 0 에서의 최대 노드 개수 + level 1 에서의 최대 노드 개수 + $\displaystyle \cdots$+ level $\displaystyle h$ 에서의 최대 노드 개수 = $\displaystyle 2^0+2^1+\cdots+2^h=2^{h+1}-1$이다.

(3-2)레벨 $\displaystyle i$의 단말 노드는 레벨 $\displaystyle i+1$에 0 개의 자식 노드를 생성하고, 레벨 $\displaystyle i$의 내부 노드는 레벨 $\displaystyle i+1$에 $\displaystyle 2N_i$ 개의 자식 노드를 생성하므로,레벨 $\displaystyle i+1$의 노드 개수 = (레벨 $\displaystyle i$의 내부 노드가 생성하는 자식 노드 수) +(레벨 $\displaystyle i$의 단말 노드가 생성하는 자식 노드 수)= $\displaystyle 2N_i$이다.

(3-3)문제 (3-2)에 의해 레벨 $\displaystyle i+1$은 정확히 $\displaystyle 2N_i$개의 노드를 가져야 한다.그러나 레벨 $\displaystyle i+1$에서의 총 노드 개수는 $\displaystyle N_{i+1}+L_{i+1}$으로 나타낼 수 있으므로 $\displaystyle 2N_i=N_{i+1}+L_{i+1}$이 되어 $\displaystyle N_i=\frac{N_{i+1}+L_{i+1}}{2}$ 식을 얻는다.

(3-4)이진트리의 루트 노드를 제외한 모든 노드는 왼쪽 또는 오른쪽 이진 부분트리의 루트 노드이므로 반드시 하나의 부모 노드와 변으로 연결되어야 한다. 따라서 루트 노드를 제외하면 $\displaystyle n-1$ 개의 노드가 있으므로 정확히 $\displaystyle n-1$ 개의 변이 필요하다.

(3-5)$\displaystyle s$를 이진트리에 있는 내부 노드 개수라 하자.이진트리의 모든 내부 노드는 2개의 자식 노드를 가지므로 이진트리에 있는 모든 변의 개수는 $\displaystyle 2s$이다.이진트리의 총 노드 개수는 $\displaystyle n+s$이므로 문제 (3-4)에 의해 이진트리에 있는 변의 개수는 $\displaystyle n+s-1$이다.따라서, $\displaystyle 2s=n+s-1$, 즉 $\displaystyle s=n-1$이다.

(3-6)문제 (3-5)로부터 $\displaystyle n$개의 단말 노드를 가지는 이진트리는 총 $\displaystyle 2n-1$개의 노드를 갖는 것을 알 수 있다. 루트 노드 하나만 있는 레벨 0 외에는 모든 레벨이 최소 2개의 노드를 가져야 한다. 따라서 $\displaystyle 2n-2$개의 노드로 만들 수 있는 최대 개수의 레벨은 $\displaystyle n-1$개이므로, $\displaystyle n$개의 단말 노드를 가지는 이진트리는 최대 $\displaystyle (n-1)+1=n$개의 레벨, 즉 최대 $\displaystyle n-1$의 높이를 가질 수 있다.