《数据结构与算法分析(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就算满(是一种性质),该定义下,你能表示的性质更多。