在二叉树中,根节点的深度是0还是1 啊!在教材上是0,而老师讲的是1

如题所述

根的深度和高度为0

《数据结构与算法分析(Mark Allen Weiss)》:

深度是从根到节点的唯一路径长,根的深度为0;高度为从节点到一片树叶的最长路径的长,树叶的高度为0。

此外,树是现实中抽象出的,倒过来画的,所以往下是高度,往上是深度。

从逻辑上来说,根的深度与高度是0(树的深与高就定了)。它们是一个距离概念,是两节点的差。

从1开始有一些应用上的好处,比如说高为3层(起始为1)的满二叉树(7个元素),它的节点数就是2^3-1,也即高h则节点数2^h-1。而国外该树的高是2,那么就是2^(2+1)-1,没那么简洁,又比如平衡树的节点数范围也是同理。

另外,国内某些教材似乎有意无意地模糊了高度和深度的概念,体现在某些编程里,明明是从中间节点往下算,算的是高度,却说是在算深度(不影响最终程序结果,但逻辑混乱了)。然后一些教材里引入了层次的概念,我觉得挺好,层次其实就从0开始算的高度加1。

再回到最开始,根节点到底该不该有高度呢?这实质上取决于你逻辑上的参照系,如果根是逻辑上的根,那么参照物就是自己,那么高度和深度就该是0。如果根节点是起始节点的意思,参照物是地面(null)那么根节点的高就是1,但逻辑上的问题又出现了,那它高为1,深度咋还为1呢?这时候高和深度其实混在一起了。国内给了一种没错但是逻辑混乱的定义:树的深度(高度)是树中所有节点的最大层次。

…………………………………………

这里再提一句,国外的满二叉树也不是国内的定义,而是任意节点的度是2或0就算满(是一种性质),该定义下,你能表示的性质更多。

温馨提示:答案为网友推荐,仅供参考
第1个回答  2011-11-12
完全二叉树的深度,深度大于等于1.追问

哦 这个情况啊谢谢

本回答被提问者采纳
第2个回答  2011-11-13
应该是1 你可以找一下有关树的深度的公式验证一下。
相似回答