Submit My Question - Recent Questions - Recent Answer
Msdn China Tech >> 专题开发,技术,项目 >> 数据结构,算法

一个证明题

Answer the following questions about a non-empty binary tree of N nodes and height H:
Prove that N ≤ 2H+1 - 1.
怎么证谢谢。
[139 byte] By [rayoko-靖康] at [2008-5-2]
«« 我想问一下为什么我的分数总是在一点一点的减少?
»» 各位前辈,请问迅雷和腾讯你们选择谁?
# 1
可以用induction来证明
Base case H=0:

N1 ≤ 2H1+1 - 1
N2 ≤ 2H2+1 - 1

N - 1 ≤ 2H1+1 + 2H2+1 - 2

N ≤ 2H1+1 + 2H2+1 - 1
≤ 2(H-1)+1 + 2(H-1)+1 - 1
≤ 2H+1 - 1
qt_pixie-QT_pixie at 2007-10-19 > top of Msdn China Tech,专题开发,技术,项目,数据结构,算法...
专题开发,技术,项目
数据结构,算法

专题开发,技术,项目 Hot Topic

专题开发,技术,项目 New Topic

专题开发,技术,项目

Java / MSDN / Linux Tech / PHP Tech / MSDN DotNet / MSDN TECH / Health Library / Programmers Tech / visual basic Tech / Developer Tech / Ipod faqs / Msdn China Tech

Site Classified