代码之家 › 专栏 › 技术社区 › Alex Mullans

全二叉树节点高度和的归纳证明

proof tree

Alex Mullans · 技术社区 · 14 年前

我想通过归纳法来证明以下几点:

sum(k*2^(H-k), k = 0 .. H) = N-H-1

但是,这个问题是不同的,因为替换H+1会改变求和中的每个项。。。所以我认为这种技术行不通。

这是一个家庭作业问题。。。所以我显然不期待一个完整的解决方案。但是,我不太确定在哪里求和,所以我在寻找其他的归纳方法。

1 回复 | 直到 14 年前

Tim 14 年前

假设树是满的,您仍然可以通过归纳来做一些传统的证明。只要写下如果它能达到一定高度 H ,那么你知道高度之和是 N-H-1 H+1 . 考虑:

推荐文章

root · 计数算法

1 年前

Ash · 递归列表拆分和索引

2 年前

Someone · 如何实际删除节点?

2 年前

bb ef · 如何使用递归从列表中删除某些内容?python

6 年前

Linkmaster · 在用于BST的类中是否可能有类成员变量BST?

6 年前

Adam Morad · 方案更改树值

6 年前

A Akshat · 如何为函数中的结构分配动态内存插槽,该结构可以从程序中的任何位置访问

6 年前

johnny 5 · 角度将ViewChild绑定到类中的属性

6 年前

user2467011 · 为什么给定的二叉树是用空节点构造的?

6 年前

Yuki.kuroshita · 从二叉树中删除节点及其所有子节点,而不使用树数据结构

6 年前