이것은 숙제이고 그것에 쓸 시간이별로 없었습니다.하지만 저는 답을 알고 약간의 도움이 필요합니다. pl30얼마나 많은 노드가 레벨 n에 이진 트리를 가질 수 있습니까? 유도를 사용하여 대답을 증명하십시오
나는 우리가 가지고있는 것으로 생각하고 있습니다. :
1 노드 ----> 1 급
2,3- 노드 ----> 2 단계
3,4,5,6,7 노드 ----> 3 급
4,5,6, ..., 15 노드 ----> 레벨 4
5,6,7,8,9, ..., 31 개 노드 ----> 레벨 5
노드 간격 (분 = X 노드 TO 초 = 2)^X - 1 개 노드 (들)] 내가
내가 N 번째 케이스와 N + 1 번째 사건을 증명하기 위해 당신이 유도를 사용하는 기억으로. 그리고 우리는 어떤 N에 대해서도 N + 1 레벨이 정확하게 두 배 더 많음을 봅니다. 따라서, 2 ^로 나타낸 (N + 1)/2^N = 2 노드의 총 개수 = 0 N까지 N에서 합을 취함으로써 발견 될 수
- 1 아마 N
너^2의 좀 더 결정적이고 자세한 답변을 원하지만 그 요지는 있습니다.
당신이 바로 그것을 가지고처럼 소리를 완료하는 방법에 혼란 스러워요에 X 지금부터 레벨
을 대표하는 곳. 이진 트리가 가질 수있는 노드의 최소 금액은 N이고 최대는 2^N-1
유도는 어떨까요? –
당신이 보여준 것은 귀납에 의한 증거입니다. 성명서에서와 같이 좀 더 공식화해야합니다. – atx
내가 N + 1에서 말하기를 원한다면 [N + 1에서 (2^(N + 1) -1)]까지 2 값 [N + 1에서 (2^(N + 1) -1))] 그리고 평등을 증명하는 법 –
이진 트리에서 레벨 n의 노드에는 n 조상이 있습니다. 유도에 의한 증명 : Show P (0) : 레벨 0의 노드에는 조상이 없습니다. (루트이기 때문에 사실입니다.) Show P (1) : 레벨 1의 노드에는 상위 노드가 하나 있습니다. (이것은 사실이며, 조상은 루트이고 그 아버지는 레벨 0에 있습니다.) P (K) 가정 : 레벨 K의 노드는 K 조상을가집니다. 그 아버지는 레벨 K - 1에 있습니다.Prove P (K + 1) : 레벨 K + 1의 노드는 레벨 K의 노드보다 하나 더 상위의 조상을가집니다. K + 1 번째 요소는 레벨 (K +1) -1 또는 수준 K
이 질문은 그래프 이론 및 수학에 관한 주제이기 때문에이 질문은 논점이 아닌 것처럼 보입니다. –