树的高度于深度不一样，高度从1数起，深度从0数起，对吗？

论坛 › 期权论坛 › 期权

 匿名用户1024  2021-5-30 23:18  18203  5

《数据结构与算法》高等教育出版社，4.2 二叉树的主要性质中有如下内容：
……
性质5：高度(height)为k(深度(depth)为k-1)的二叉树至多有2^k-1个结点
其中，二叉树的高度定义为二叉树中层数最大的叶结点的层数加1，深度定义为二叉树中层数最大的叶结点的层数
性质6：有n个结点(n > 0)的完全二叉树的高度为h = (ceil)(log2(n+1))，深度为h - 1
按这种说法深度和高度不一样。。。无语了

回复

分享到 :

0 人收藏

5 个回复

倒序浏览

2^#

有关回应 16级独孤 | 2021-5-30 23:18:39

维基百科的定义：

深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；

stackoverflow的回答
What is the difference between tree depth and height?

支持反对回复

3^#

有关回应 16级独孤 | 2021-5-30 23:18:40

不同的作者可能采取不同的定义，你需要到书的前面去找这本书内是怎么定义的。

支持反对回复

4^#

有关回应 16级独孤 | 2021-5-30 23:18:41

国内教材参差不齐，很多都是把高度和深度混淆了。
其实直接从字面意思理解就好：
深度：从根结点开始，往下。
高度：到叶子结束，“往上”。

支持反对回复

5^#

有关回应 16级独孤 | 2021-5-30 23:18:42

这个问题没有什么意义，就是个定义而已

支持反对回复

6^#

有关回应 16级独孤 | 2021-5-30 23:18:43

谢邀。
其实有不少书籍里面这两个概念都是一个意思，如下图：

的确不用在意这一点。

另外，题主可以看看《算法》第四版(美 Robert Sedgewick著) ，虽然名字叫算法，但是大部分是讲数据结构的，相信对你有帮助

支持反对回复

16级独孤

匿名用户1024

积分:136515

帖子:27303

精华:0

+ 关注私信

期权论坛

期权论坛

期权网络科技版权所有: 关于我们; 联系我们; 加入我们; 反馈问题; 免责声明; 积分充值

统一社会信用代码: 积分规则; 网站地图; 爱文库; 下属网站

官方: 新浪微博; 微信公众号
◆

下载: 表情包; App下载

期权论坛

期权论坛

QQ咨询|关于我们|Archiver|手机版|小黑屋|( 辽ICP备15012455号-4 ) Powered by 期权论坛 X3.2 © 2001-2016 期权工具网&期权论坛 Inc.