3
목록을 통해 트리를 나타냅니다.leafs의 순서가 왼쪽에서 오른쪽으로 정해지면 얼마나 많은 이진 트리가 있습니까?
리프의 수가 2 개인 경우 A와 B입니다. 그런 다음 하나의 트리 (A B) 만 있습니다.
리프의 수가 3이면 A, B 및 C입니다. 그런 다음 두 개의 트리 ((A B) C)와 (A (B C))가 있습니다.
N 개의 리프가있는 경우 몇 개의 트리가 있습니까?
A
답변
6
N 인 이진 트리의 수를 T(N)으로합시다.
우리는 즉시 볼 수있는 것처럼 T(1) = T(2) = 1을 가지고 있으며 N > 2에 대해 우리는 더 적은 잎을 가진 두 개의 하위 트리를 얻을 수 있습니다. 또는 동등하게, 우리는 각각 k과 N-k 잎이 아닌 두 개의 비어 있지 않은 이진 트리에서 N 잎을 가진 이진 트리를 어셈블 할 수 있습니다. 두 하위 트리가 모두 비어 있지 않은 조건은 1 <= k <= N-1으로 변환됩니다. 그래서 우리는 재귀에게 재귀는 아직 알 수없는 경우
N-1
T(N) = ∑ T(k) * T(N-k)
k=1
을 가지고, 처음 몇 값
1,1,2,5,14,42,132,429,1430,4862,16796
C(n) = (2*n)!/(n! * (n+1)!)
그래서 재귀보다 훨씬 빨리 계산할 수있다
T(N) = C(N-1)
, 하나에 의해 상쇄, 이들은 Catalan numbers을 것을 발견한다.
+1
+1, 좋은 설명. 나는 카탈로니아 어를 좋아한다! 많은 것들이 그 안에 들어 있습니다. – amit
+0
내부 노드의 정도에 대한 조건이 있습니다. 일부 하위 트리의 루트가 차수가 1 인 경우 하위 트리를 두 개의 비어 있지 않은 하위 하위 트리로 나눌 수 없습니다. –
+0
@OmriBarel 물론 리프가 아닌 모든 리프에는 두 개의 자식이 있어야합니다. 그렇지 않으면 모든 'N> 0'에 대해 ℵ_0 개의 트리가 있습니다. –
*** "목록을 통해 트리를 표현합시다."*** 어떻게해야할까요? –
다음은 힌트입니다. 잎의 수가 2의 거듭 제곱이면 잎이 지정된 순서로 하나의 이진 트리가 있습니다. – gogognome
@gogognome 나는 그것이 사실이라고 생각하지 않는다. 예를 들어 http : //draw.to/DfUt2p를 확인하십시오. 균형이 맞지 않는 8 리프 2 진 트리를 보여줍니다. –