[자료구조] 이진트리의 성질*

노드의 차수 : 어떤 노드가 가지고 있는 자식 노드의 개수

전체 트리의 차수 : 트리가 가지고 있는 노드의 차수중에 가장 큰값

트리의 레벨 : 트리의 각층에 번호를 매기는 것, 루트의 레벨은 0또는 1이고 한층씩 내려갈 수록 1씩증가

트리의 높이 : 트리가 가지고 있는 최대레벨을 말한다.

 

이진트리의 성질

- N개의 노드를 가진 이진트리는 N-1개의 간선을 가진다.

높이가 h인 이진트리는 최소 h개의 노드를 가지며, 최대 2^(h+1)-1 개의 노드를 가진다.(루트의 레벨을 0이라 가정)

- 노드의 개수가 1 이상인 이진트리에서 차수(분지수)가 i인 노드의 개수를 Ni라고 할때, N0 = N2 +1 이다.

증명 ) n = n0+n1+n2 (전체 노드의 개수는 차수가0인 노드와 1인노드와 2인 노드의 개수를 합친 것과 같다.)

        m(엣지(간선)의 개수) = n-1

        m = n1*1 + 2*n2 (간선의 개수는 차수가 1인노드의 차수 : 어떤 노드가 가지고 있는 자식 노드의 개수

 

전체 트리의 차수 : 트리가 가지고 있는 노드의 차수중에 가장 큰값

 

트리의 레벨 : 트리의 각층에 번호를 매기는 것, 루트의 레벨은 0또는 1이고 한층씩 내려갈 수록 1씩증가

 

트리의 높이 : 트리가 가지고 있는 최대레벨을 말한다.

 

 

 

이진트리의 성질(루트의 레벨을 0이라 가정)

 

- N개의 노드를 가진 이진트리는 N-1개의 간선을 가진다.

 

높이가 h인 이진트리는 최소 h개의 노드를 가지며, 최대 2^(h+1)-1 개의 노드를 가진다

 

- n개의 노드를 가지는 이진트리의 높이는 최대 n-1이거나 log2(n+1)이다.

 

- 노드의 개수가 1 이상인 이진트리에서 차수(분지수)가 i인 노드의 개수를 Ni라고 할때, N0 = N2 +1 이다.

 

증명 ) n = n0+n1+n2 (전체 노드의 개수는 차수가0인 노드와 1인노드와 2인 노드의 개수를 합친 것과 같다.)

        m(엣지(간선)의 개수) = n-1

        m = n1*1 + 2*n2 (간선의 개수는 차수가 1인 노드의 개수와 차수가 2인 노드의 개수에 2배를 한 것과 같다.)

        위 식으로부터 n0 = n2 +1 을 얻을 수 있다.

 

 

 

 

작성중..